Mỗi số đều mang một ý nghĩa vô cùng đặc biệt. Theo quan niệm của nhiều người, số 5 là một số đặc biệt trong các số đặc biệt; số 5 tương ứng là số sinh, đại diện cho sự chính trực, một số đại cát, đại lợi. Vì đam mê với các con số nên Tít đã tìm hiểu rất nhiều cổ tích về số 5. Hôm nay, trong tiết Tin học của lớp 10 chuyên Tin. Thầy giáo đưa ra yêu cầu đếm các số nguyên tố trong đoạn từ ~ l ~ đến ~ r ~. Tít thấy nhiệm vụ này khá quen thuộc nên quyết định thử thách mình với yêu cầu đếm xem trong đoạn ~ l ~ đến ~ r ~ có bao nhiêu số là số nguyên tố và đồng thời có tổng các chữ số chia hết cho 5. Tít gọi các số đặc biệt này là các số siêu nguyên tố.

Yêu cầu: Em hãy giúp bạn Tít đếm xem trong đoạn từ ~ l ~ đến ~ r ~ có bao nhiêu số là số siêu nguyên tố.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương ~ t≤3×10^5 ~ là số lượng Test.
• ~ t ~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~ l, r (l≤r≤3×10^6) ~ theo thứ tự, phân tách nhau bởi dấu cách.

Kết quả:

• Ghi ra ~ t ~ dòng, mỗi dòng ghi một số là số lượng số siêu nguyên tố có trong đoạn ~ [l;r] ~, tương ứng theo thứ tự dữ liệu Test đầu vào.

Ví dụ:

Input

3
1 10
4 20
6 15 

Output

1
2
0 

Giải thích:

• Trong đoạn [1;10] có 1 số siêu nguyên tố là 5.
• Trong đoạn [4;20] có 2 số siêu nguyên tố là 5 và 19 (1+9 = 10).
• Trong đoạn [6;15] không có số siêu nguyên tố nào.

Ràng buộc:

• 20% số test có ~ 1≤t≤100; l,r≤200 ~.
• 20% số test tiếp theo có ~ 1≤t≤10^3; l, r≤2.10^3 ~.
• 30% số test tiếp theo có ~ 1≤t≤104; l, r≤2.105 ~.
• 30% số test cuối cùng có ~ 1≤t≤3.105; l,r≤3.10^6 ~.