First define a special K-Base number system. For each number in this system, the number can not contain more than K dights. And From left to right, the i-th digits can use dight 0 to i(A dights more than 9 use A,B,C…… stands for)
For example:
If K=3, the first 15 number is 000,001,002,003,010,011,012,013,020,021,022,023,100,101,102
Now please convert the special K-based number and decimal number.
Input
Multi case ending in EOF.
For each case, the first line has two numbers Q and K, indicate K-based number system(2<=K<=16) and Q questions.(1<=Q<=20)
Next Q lines, each line has two number C and N (if C=2, N will include Uppercases)
Output
For each question:
If C=1 output the N-th number in the K-based number system.
If C=2 for a K-based number, output in the system, the position of the number(the first pos is 1)