Số Đặc Biệt Thứ K

Xem PDF

Điểm: 600 (p) Thời gian: 6.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một dãy số nguyên dương vô hạn \(A_1, A_2, ... A_N\) có một trong hai tính chất như sau (hoặc là có cả hai) :

  • Tổng các chữ số của \(A_i\) chia hết cho \(m\).
  • Chữ số cuối cùng của \(A_i\)\(p(0 \le p \le 9)\).
  • Và với mọi \(i > 0\) thì \(a_{i} > a_{i - 1}\).

Yêu cầu : Hãy in ra số thứ \(K\) trong dãy \(A\) và cho biết phần dư của \(\sum_{i = 1}^k A_i\) khi chia cho \(10^9 + 9\), Đề bài đảm bảo \(a_{K} \le 10^{18}\).

Input

  • Dòng đầu tiên là một số nguyên dương \(T(T \le 81).\)
  • \(T\) dòng tiếp theo, mỗi dòng gôm 3 số nguyên \(K,m,p\) với \((K \le 10^{18}, m \le 200, 0 \le p \le 9)\) .

Output

  • Gồm \(T\) dòng, mỗi dòng gồm 2 số nguyên là đáp án của dòng truy vấn tương ứng.

Example

Test 1

Input
3
16 8 9
42 13 6
28 32 1
Output
79 668
266 6000
271 3808
Note

**Giải thích : **
Trong lần thử nghiệm đầu tiên ta có dãy A là : 8 9 17 19 26 29 35 39 44 49 53 59 62 69 71 79 ...
Vậy số thứ 16 là số 79 và 8 + 9 + 17 + 19 + ... + 79 = 668.


Bình luận

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