Cho hai số nguyên dương ~n~ và ~h~. Tháp lũy thừa cơ số ~n~, chiều cao ~h~, ký hiệu là ~T(n, h)~, được định nghĩa như sau:

• ~T(n, 1) = n~;

• ~T(n, h) = n^{T(n, h-1)}~ với mọi ~h \ge 2~.

Nói cách khác, ~T(n, h)~ là một tháp gồm ~h~ tầng, mỗi tầng đều có cơ số ~n~; số mũ của mỗi tầng (trừ tầng trên cùng) chính là giá trị của toàn bộ phần tháp nằm phía trên nó. Ví dụ: ~T(2, 1) = 2~, ~T(2, 2) = 2^2 = 4~, ~T(2, 3) = 2^{T(2, 2)} = 2^4 = 16~, ~T(2, 4) = 2^{16} = 65\,536~.

Tháp lũy thừa lớn lên rất nhanh: ~T(2, 5) = 2^{65\,536}~ đã có ~19\,729~ chữ số, còn ~T(2, 6)~ có số chữ số lớn hơn ~10^{19\,727}~, không thể viết ra hết. Tuy vậy, chữ số tận cùng của nó vẫn tìm được.

Cho ~q~ truy vấn, mỗi truy vấn gồm ba số nguyên dương ~L, R, h~. Với mỗi truy vấn, hãy tính tổng các chữ số tận cùng của ~T(n, h)~ khi ~n~ chạy từ ~L~ đến ~R~.

Input

• Dòng đầu tiên: số nguyên ~q~ ~(1 \le q \le 10^5)~ là số truy vấn.

• ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~L, R, h~ ~(1 \le L \le R \le 10^{18};\ 1 \le h \le 10^{18})~.

Output

Với mỗi truy vấn, in ra một số nguyên là tổng các chữ số tận cùng cần tìm, mỗi truy vấn trên một dòng.

Scoring

Sample Input 1

4
1 5 1
1 5 2
1 5 3
2 2 100

Sample Output 1

15
23
25
6

Notes

• Truy vấn 1: ~T(n, 1) = n~ nên các chữ số tận cùng là ~1, 2, 3, 4, 5~, tổng bằng ~15~.

• Truy vấn 2: ~T(n, 2) = n^n~, lần lượt là ~1, 4, 27, 256, 3125~, các chữ số tận cùng là ~1, 4, 7, 6, 5~, tổng bằng ~23~.

• Truy vấn 3: ~T(2, 3) = 2^4 = 16~, ~T(3, 3) = 3^{27} = 7\,625\,597\,484\,987~, ~\dots~ Các chữ số tận cùng là ~1, 6, 7, 6, 5~, tổng bằng ~25~.

• Truy vấn 4: ~T(2, 100)~ có chữ số tận cùng là ~6~.