TLEoj Contest #03 - Số tuyệt vọng

Điểm: 2000 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

flo

Dạng bài

Hôm nay trên đường về nhà, Sayu-chan bỗng nghĩ ra một loại số mới và nó mang tên là số tuyệt vọng. Một số nguyên dương $N$ được gọi là số tuyệt vọng nếu nó chứa chính xác $K$ chữ số khác nhau.

Sayu-chan hiện tại cũng đang có hai số nguyên dương $L$ và $R$ . Cô ấy muốn biết được tổng của các số tuyệt vọng trong đoạn $[L,R]$ . Bạn hãy giúp Sayu-chan nhé.

Input, Output và Subtasks

Input

Dòng thứ nhất gồm 1 số nguyên dương $T$ là số testcase ( $1\le T\le 10^5$ )
Sau đó là $t$ dòng, mỗi dòng nhập 3 số nguyên dương $L,R,K$ ( $1\le L\le R\le 10^{18},1\le K\le 10$ )

Output

Xuất ra $T$ dòng, mỗi dòng gồm 1 số tương ứng với kết quả từng testcase. Vì kết quả có thể rất lớn nên hãy xuất kết quả sau khi $mod\ 1234567891$

Scoring

Subtask 1 ( $30\%$ ): $1\le L\le R\le 10^6$
Subtask 2 ( $40\%$ ): $T\le 20$
Subtask 3 ( $30\%$ ): Không có ràng buộc gì thêm

Sample

Input

2
10 34 1
24 513 2

Output

66
37458

Note

Ở ví dụ 1, các số tuyệt vọng là $11,22,33$ . Tổng của chúng là $11+22+33=66$ .

Bình luận

Không có bình luận nào.