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$ được gọi là số sinh nhật nếu nó chứa các chữ số $2, 7, 9$ xuất hiện bằng nhau và ít nhất $1$ lần.

Ví dụ số ~2709~ là một số sinh nhật.

Để 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ố sinh nhật 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^{100})~.

Dữ liệu ra

Gồm ~Q~ dòng là đáp án của ~Q~ câu hỏi chia dư cho $10^9 + 2709$.

Ví dụ

Input

3
1 20 
100 1000 
1 100270908 

Output

0
6
5780151

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^{100}~.
• Subtask 3 (30% số điểm): Không có ràng buộc gì thêm.