It is possible to number all the words that could be formed from a specified alphabet. One way to do it is to put the words in order based on length, with words of common length ordered alphabetically. Using this scheme, if we use the alphabet consisting of just the 3 letters 'a', 'b', and 'c' then the words are numbered:

1:a 2:b 3:c 4:aa 5:ab 6:ac 7:ba 8:bb etc.

There are an infinite number of possible words, but each has its own positive number. We want to be able to find the word that corresponds to any given number N. The alphabet to be used is the first A letters of the normal lowercase alphabet, with their usual alphabetical ordering.

Input

First line contains an integer T (less than 1000) denoting the total number of test cases. Each test case consists of a single line of input having two integer A (2 <= A <= 26) and N (1 <= N <= 2000000000). 

Output

For each test case print the required string in a single line.

Example

Input:
2
3 13
26 2000000000

Output:
aaa
flhomvx