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