Số SDIGIT

Minh đang nghiên cứu về số học thì thấy rất thích các số có tổng các chữ số là số nguyên tố. Minh gọi các số đó là SDIGIT.

Một số có $k$ chữ số thì gọi là số có độ dài $k$. Minh đang có nhiệm vụ đi tìm tất cả các số SDIGIT có độ dài từ $l$ đến $r$. Vì số lượng số SDIGIT quá nhiều nên anh ấy không đếm nổi được.

Yêu cầu: Hãy viết một chương trình giúp Minh biết từ độ dài $l_i$ đến $r_i$ có bao nhiêu số mà tổng các chữ số của chúng là 1 số nguyên tố.

Vào từ file văn bản SDIGIT.INP

• Dòng đầu là số $q$ – số truy vấn cần thực hiện.
• $q$ dòng sau, dòng thứ $i$ chứa 2 số $l_i$, $r_i$.

Ghi ra file văn bản SDIGIT.OUT

• Mỗi dòng $i$ là một đáp án cho truy vấn thứ $i$.

• 80% số điểm của bài: $1 \le l_i, r_i \le 6$, $q \le 10$.
• 100% số điểm của bài: $1 \le l_i, r_i \le 250$, $q = 1$.