Một số nguyên dương ~x~ được gọi là S-digit nếu như tổng các chữ số của ~x~ là một số nguyên tố. Nhắc lại, số nguyên tố là số nguyên dương có duy nhất hai ước số phân biệt là ~1~ và chính nó (số ~1~ không phải số nguyên tố).

Yêu cầu

Cho ~Q~ truy vấn, mỗi truy vấn có dạng ~l, r~ (~1 \leq l \leq r \leq 250~). Với mỗi truy vấn, đếm số lượng số S-digit có số lượng chữ số không nhỏ hơn ~l~ và không lớn hơn ~r~ (thuộc khoảng ~[l, r]~). Kết quả in ra là phần dư trong phép chia của kết quả tìm được cho ~10^9 + 7~.

Input

Vào từ tệp văn bản SDIGIT.INP gồm:

• Dòng đầu tiên chứa số nguyên dương ~Q~ (~1 \leq Q \leq 10~).
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l~ và ~r~ cách nhau bởi dấu cách, biểu diễn một truy vấn (~1 \leq l \leq r \leq 250~).

Output

Đưa ra tệp văn bản SDIGIT.OUT ~Q~ dòng, mỗi dòng xuất ra một số nguyên. Với truy vấn thứ ~i~, xuất ra phần dư của phép chia giữa kết quả của truy vấn tương ứng và ~10^9 + 7~ trên dòng ~i~.

Ví dụ

2
1 1
1 2

4
37

Ràng buộc

• ~80\%~ số test tương ứng với ~80\%~ số điểm có ~Q \leq 10~ và ~l \leq r \leq 6~.
• ~20\%~ số test còn lại tương ứng với ~20\%~ số điểm có ~Q = 1~ và ~l \leq r \leq 250~.