Cái đẹp trong mắt mỗi người là khác nhau và Gấu cũng thế, Gấu say mê với những con số đẹp (tất nhiên là cũng có con gái đẹp). Con số theo Gấu là đẹp được định nghĩa như sau:

Một số nguyên dương $X$ gọi là số đẹp nếu nó thỏa một trong hai điều kiện:

• Tổng chữ số của $X$ chia hết cho $m$.
• Chữ số cuối trong biểu diễn thập phân của $X$ là $p$.

Ví dụ với $m = 8, p = 9$ thì ~X \in \{8, 9, 17, 19, \dots \}~ là những con số đẹp.

Một tập hợp các số đẹp được sắp xếp tăng dần như thế gọi là dãy số đẹp.

Để phục vụ cho việc gì đó, mỗi ngày trong ~Q~ ngày Gấu cần phải tìm số đẹp thứ $K$ trong dãy số đẹp ấy, đồng thời cũng cần tính tổng các giá trị từ số đẹp đầu tiên đến số đẹp thứ $K$ chia dư cho $10^9 + 2709$, biết dãy số được đánh số từ $1$. Bạn hãy giúp Gấu nhé.

Dữ liệu vào

• Dòng đầu tiên gồm số nguyên ~Q~ ~(1 \leq Q \leq 10^3)~.
• ~Q~ dòng sau, mỗi dòng gồm ba số nguyên ~K, m, p~ ~(1 \leq K \leq 10^{10}, 1 \leq m \leq 200, 0 \leq p \leq 9)~.
• Dữ liệu đảm bảo số đẹp thứ $K$ không vượt quá $10^{18}$.

Dữ liệu ra

Gồm ~Q~ dòng là đáp án của ~Q~ câu hỏi.

Ví dụ

Input

3
16 8 9
42 13 6
28 32 1

Output

79 668
266 6000
271 3808

Note

Với $m = 8, p = 9$, dãy số đẹp là ~\{ 8, 9, 17, 19, 26, 29, 35, 39, 44, 49, 53, 59, 62, 69, 71, 79 \}~.

Vậy số đẹp thứ $16$ là $79$ và tổng các số đẹp là $668$.

Tính điểm

• Subtask 1 (30% số điểm): ~1 \leq Q \leq 3, 1 \leq K \leq 100~.
• Subtask 2 (40% số điểm): ~1 \leq Q \leq 3, 1 \leq K \leq 10^{10}~.
• Subtask 3 (30% số điểm): Không có ràng buộc gì thêm.