Cái đẹp trong mắt mỗi người là khác nhau và Gấu cũng thế, Gấu say mê với những con số đẹp (tất nhiên là cũng có con gái đẹp). Con số theo Gấu là đẹp được định nghĩa như sau:

Một số nguyên dương $X$ gọi là số bất thường nếu nó thỏa tổng chữ số và tổng bình phương chữ số nguyên tố cùng nhau.

Ví dụ số $23$ có tổng chữ số là $5$, tổng bình phương chữ số là $13$ là hai số nguyên tố cùng nhau nên $23$ là số bất thường.

Để phục vụ cho việc gì đó, mỗi ngày trong ~Q~ ngày Gấu cần phải đếm số lượng số bất thường trong đoạn ~[L, R]~. Bạn hãy giúp Gấu nhé.

Dữ liệu vào

• Dòng đầu tiên gồm số nguyên ~Q~ ~(1 \leq Q \leq 10^5)~.
• ~Q~ dòng sau, mỗi dòng gồm ba số nguyên ~L, R~ ~(1 \leq L \leq R \leq 10^{18})~.

Dữ liệu ra

Gồm ~Q~ dòng là đáp án của ~Q~ câu hỏi.

Ví dụ

Input

3
1 20 
100 1000 
1 100270908 

Output

6
368
40863915

Tính điểm

• Subtask 1 (30% số điểm): ~1 \leq Q \leq 3, 1 \leq L \leq R \leq 10^6~.
• Subtask 2 (40% số điểm): ~1 \leq Q \leq 3, 1 \leq L \leq R \leq 10^{18}~.
• Subtask 3 (30% số điểm): Không có ràng buộc gì thêm.