Giải bài trực tuyến

Để 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 <= 1e18.

- Trong 30% số test, N <= 1e5.

- Trong 25% số test, 1e5 < N <= 1e18 và T = 0.

- Trong 25% số test, 1e5 < N <= 1e18 và T = 1.

Trong lúc thi bài của bạn chỉ được chấm với test ví dụ.

Example

Input:
1
0 1 1

Output:
1

Input:
1
1 10 9

Output:
8

Input:
3
0 10 9
0 10 10
1 10 9 

Output:
10
2
8