Dictionary Entries

We heartily thank Clive Fraser for this problem!

Ann and Bob are always inventing new games. One day they came across a set of Scrabble tiles and decided to invent another game which would allocate scores to different letters. They decided that letters would become available to players in the same proportions as they occur in the English Language. They decided that each of the 26 letters should have a different score and that the most common letters would have the smallest scores. After some research they discovered that the frequency order of letters in the English Language is ETAOINSRHDLUCMFYWGPBVKXQJZ; where E is the most common letter and Z is the least common letter. They used this list to decide on the following scores for the letters.

E  1     T  2     A  3     O  4     I  5     N  6     S  7     R  8     H  9     D  10     L  11     U  12     C  13
M  14    F  15    Y  16    W  17    G  18    P  19    B  20    V  21    K  22    X  23     Q  24     J  25     Z  26

Ann and Bob decided not to use actual English Words in their game. Instead they decided to define a word (for the purpose of the game) as follows. A word is a string of 1 or more uppercase letters taken from the English alphabet. No two consecutive letters in the word can be the same and all words must have a score of less than 80; where the score for the word is just the sum of the scores of its individual letters. Examples of valid words are: K (which has a score of 22); CODE (which has a score of 13 + 4 + 10 + 1 = 28); and JFGLD (which has a score of 25 + 15 + 18 + 11 + 10 = 79). Examples of invalid words are FOOD (which has consecutive letters which are the same, i.e. both O) and ZEZEZ (which has a score of 26 + 1 + 26 + 1 + 26 = 80 which exceeds the maximum allowed score).

Ann and Bob realised that some of the valid words could be quite long. It could be time-consuming to work out the scores for these words and mistakes would be fairly common. To deal with this problem they decided to create a computer dictionary. This would contain all valid words, in lexicographic order, together with their scores. The dictionary would not only provide correct scores for words but would recognise invalid words and would provide other types of information; such as the possible endings which could be attached to a given stem in order to create a word with a specified total score. Details of the rest of the game are not relevant to this problem. We are concerned only with the computer dictionary. For example, there are 23 words in the dictionary with a score of exactly 7. If we take these words out of the dictionary, while keeping their lexicographic order, we obtain the following list.

AEA, AETE, AO, EAET, EATE, EIE, EN, EOT, ETAE, ETEA, ETETE, ETO, IT, NE, OA, OET, OTE, S, TAT, TEAE, TEO, TI, TOE

We see that AEA is in position 1, ETEA is in position 10 and TOE is in position 23.

In this problem you will be given several sets of scores S and positions P. You are to consider the list of words (in lexicographic order) having a score of S and are asked to find the word that appears at position P in this list.

The first line of the problem will be a single integer T denoting the number of test cases. Each test case will consist of two integers S and P, separated by a space. For each test case you must find the word at position P in the lexicographically ordered list of words having a score of S. Give all answers, separated by spaces, as a single string.

Example:

input:
5
7 23
9 60
19 13722
27 1594672
30 8515277

answer:
TOE TEN RANT TNTATIS TNETEASEAETE