After obtaining a secret scroll, King Kala along with Commander in Chief Rajan is busy making war strategies. He has entrusted the job of making wartime communication ciphers on his most two mosy trusted generals, Minister Rana and Minister Dude. Minister Rana comes up with the idea of using Fibonacci Strings as the cipher.
The Fibonacci string (consisting only of lower case characters) follows the pattern as shown below.
a b b c d f i n v i d l o z n m . . .
Minister Dude though wants the cipher to be more secure and thus decides the following strategy. He counts the frequency of the characters in a given range [L,R] in the Fibonacci String. With this, the term 'a' in the plain text is to be replaced with the most frequent term in the range [L,R]. The term ‘b’ in the plain text is to be replaced with the second most frequent term in the range and so on so as to generate the cipher. If two characters have the same frequency, the lexicographically smallest character comes first.
Help Minister Rana generate the cipher text using this method.
Input:
First line contains T, which is the number of test cases in the input.
The first line of each test case contains two space separated integers L and R denoting the range which is to be taken. The second line of each test case contains the string S (single word) which is the plain text to be enciphered.
Output:
Print the encrypted message in a separate line .
Constraints
1 <= T <= 10^4
0 <= L <= R <= 10^5
1<= | S | <=100
For range [0,4] , the fibonacci string is a b b c d.
Here, ‘b’ occurs 2 times,and ‘a’,’c’,’d’ occurs once .
Thus the frequency order is
b a c d e f g h i j k l m n o p q r s t u v w x y z
So, for the input string “abcd”, the output should be “bacd”.
For the range [1,9] , the fibonacci string is b b c d f i n v i.
Thus the frequency order is
b i c d f n v a e g h j k l m o p q r s t u w x y z
So, for the input string “abcd”, the output should be “bicd”.
