Thấy Khoa rất thích học toán, một hôm thầy giáo đã ra một bài toán cho Khoa giải như sau:

Xác định hai hàm \(f,g\) trên các số nguyên dương như sau:

• \(f(n)\) = tích các chữ số khác 0 của \(n\)
• \(g(n)\) có trị trị là:
  • \(n\) nếu n<10
  • \(g(f(n))\) ngược lại
    Khoa cần xử lý \(Q\) truy vấn, trong mỗi truy vấn sẽ được cung cấp 3 số nguyên \(l,r,k\). Khoa cần in số lượng số nguyên \(x\) nằm giữa \(l\) và \(r\), trong đó \(g(x)=k\).

Input

• Dòng đầu tiên chứa số nguyên \(Q\) \((1 \le Q \le 2 \times 10^5)\) đại diện cho số lượng truy vấn
• \(Q\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(l,r,k (1 \le l \le r \le 10^6,1 \le k \le9)\)

Output

• Với mỗi truy vấn, in ra một dòng chứa câu trả lời cho truy vấn đó.

Example

4
22 73 9
45 64 6
47 55 7
2 62 4 

1
4
0
8