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ố K-đặc biệt nếu nó thỏa:

• Số $X$ có ít nhất ~K~ chữ số phân biệt trong biểu diễn thập phân.
• Số $X$ chia hết cho ~K~ chữ số ấy.

Ví dụ số ~48~ vừa là số 1-đặc biệt vừa là số 2-đặc biệt, ~13~ là số 1-đặc biệt nhưng không phải số 2-đặc biệ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ố K-đặc biệ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, K~ ~(1 \leq L \leq R \leq 10^9, 1 \leq K \leq 9)~.

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 1
100 1000 2
1 100270908 4

Output

20
175
7417450

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