Cho $3$ số nguyên dương $l,r,k$ hãy tính $F(l)+F(l+1)+...+F(r)$ với $F(n)$ là số lần xuất hiện của chữ số $k$ trong $n$.

Dữ liệu vào

• Số nguyên dương $t$ $(1\le t\le {10}^5)$
• $t$ dòng tiếp theo, mỗi dòng chứa $3$ số nguyên dương $l,r,k$ $(1\le l\le r\le {10}^{18};0\le k\le 9)$

Dữ liệu ra

• Với mỗi dòng, hãy in ra kết quả sau khi chia lấy dư cho $1234567891$

Ràng buộc

• Substask 1 (50%): $1\le l\le r\le {10}^6$
• Substask 2 (50%): Không giới hạn gì thêm

Input 1

2
22 36 2
100 110 0

Output 1

10
12