Để hack não đội tuyển TPC (Turbo Pascal chuyên), hôm nay ngài Xuân Bách Ferguson ra cho các học trò một bài toán sau đây.

Ngài Bách có các số nguyên dương từ 1 tới ~N~. Ngài sắp xếp các số này theo thứ tự thỏa mãn điều kiện sau:

- Nếu tổng các chữ số của ~X~ nhỏ hơn tổng các chữ số của ~Y~, ~X~ đứng trước ~Y~.

- Nếu tổng các chữ số của ~X~ bằng tổng các chữ số của ~Y~ và ~X~ có thứ tự từ điển nhỏ hơn ~Y~, ~X~ đứng trước ~Y~.

Ví dụ:

+ ~227~ đứng trước ~97~ vì tổng các chữ số của ~227~ nhỏ hơn tổng các chữ số của ~97~.

+ ~11~ đứng trước ~3~ vì tổng các chữ số của ~11~ nhỏ hơn tổng các chữ số của ~3~.

+ ~9230~ đứng sau ~914~ vì ~914~ có thứ tự từ điển nhỏ hơn ~9230~.

+ ~20~ đứng trước ~200~ vì ~20~ có thứ tự từ điểm nhỏ hơn ~200~.

+ ~455168742319542531475845215624895513524875431234897216876219578923~ đứng trước ~455168742319542531495845215624895513524875411234897216876219578923~ vì ~455168742319542531475845215624895513524875431234897216876219578923~ có thứ tự từ điển nhỏ hơn ~455168742319542531495845215624895513524875411234897216876219578923~.

Ngài Bách yêu cầu học sinh giải hai bài tập sau:

- Tìm số đứng thứ ~K~ trong dãy đã được sắp xếp theo quy tắc trên.

- Tìm số thứ tự của số ~K~ trong dãy đã được sắp xếp theo quy tắc trên.

Input

Dòng đầu tiên gồm một số nguyên ~Q~ - số test trong file input

~Q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên không âm ~T~, ~N~ và ~K~

Output

Gồm ~Q~ dòng, mỗi dòng gồm một số nguyên, là kết quả của test đó. Kết quả của một test là:

- Vị trí của số ~K~, nếu ~T = 0~, hoặc

- Giá trị của số thứ ~K~, nếu ~T = 1~.

Giới hạn

- Trong tất cả các test, ~T < 2~, ~Q < 200~ và ~N \leq 10^{18}~.

- Trong 30% số test, ~N \leq 10^5~.

- Trong 25% số test, ~10^{5} < N \leq 10^{18}~ và ~T = 0~.

- Trong 25% số test, ~10^{5} < N \leq 10^{18}~ và ~T = 1~.

Sample Input 1

1
0 1 1

Sample Output 1

1

Sample Input 2

1
1 10 9

Sample Output 2

8

Sample Input 3

3
0 10 9
0 10 10
1 10 9

Sample Output 3

10
2
8