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\) là \(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

3
16 8 9
42 13 6
28 32 1

79 668
266 6000
271 3808