Cho một dãy số nguyên dương vô hạn A1,A2,...AN 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 Ai chia hết cho m. Chữ số cuối cùng của Ai là p(0≤p≤9). Yêu cầu : Hãy in ra số thứ K trong dãy A và cho biết phần dư của ∑ki=1Ai khi chia cho 109+9. Input : Dòng đầu tiên là một số nguyên dương T(T≤81). T dòng tiếp theo, mỗi dòng gôm 3 số nguyên K,m,p. 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. SampleInput 3 16 8 9 42 13 6 28 32 1 SampleOutput 79 668 266 6000 271 3808 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.