K - DICTIONARY

3

4 votes
Basics of bit manipulation
Problem

Sheldon has come up with a new language in which all words are made up of exactly  Lowercase english Letters .

For example if , then :

  • words "aaaa", "abcc", "zdsa" belong to the language as they are made up of exactly Lowercase english letters
  • words "aa", "abbbb", "abccc" don't belong as they are not made up of exactly 4 letters
  • words "Abcd", "aabD" don't belong as letters 'A' and 'D' are not lowercase.

Now consider a K-dictionary that contains all the words of this new language in asscending order.  For example if K=3, the dictionary contains words "aaa", "aab", "aac" ... "aaz", "aba", "abb" ...  "abz", "aca" and so on.

Sheldon wants to translate "The roommate agreement" into this new language. The translation is done word by word as follows :

  • If a word has position is the "Oxford English Dictionary", it translates to the word with position in the K-dictionary.
  • For example if , and a word has position in the "Oxford English Dictionary", it translates to "aad".

Clearly the above translation is a complex process and can't be done manually. So Sheldon asked his friend Howard for help. But as Sheldon always makes fun of him, Howard refused. So now you have to help Sheldon.

More formally you will be given two integers and , You have to find the word with position in the K-dictionary. You have to do this for test cases.


Input : 

  • First line of input contains , denoting number of Test cases.
  • First line of every test case contains two integers and .

Output :

For every test case print the word with position in K-dictionary. If exceeds the size of the K-dictionary, print .

Answer of every test case should start in a seperate line.


Constraints :

  • , Sum of K over all test cases does not exceed

Subtasks : 

points :

points :

  • Original constraints

 

Sample Input
5
4 1
1 26
2 5
4 4
1 30
Sample Output
aaaa
z
ae
aaad
-1
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For , dictionary contains words in order : "aaaa", "aaab", "aaac", "aaad", "aaae" .. and so on. The word at position is "aaad". So output for  is "aaad"

For , there are only 26 words "a", "b", ... "z" in the dictionary. So output for is

Editor Image

?