N different palindromes

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
A palindrome is a string that reads same in both directions: forwards and backwards. For example, the strings radar and noon are palindromes, whereas the string chef is not a palindrome as being read backwards is becomes equal to fehc, which is not equal to chef.
Let's say that the pair of indices (i, j) denotes a palindrome in some string S iff i ≤ j and the substring starting at the ith character and ending at the jth character of S is a palindrome.
Given an integer N. Your task is to construct a string S such that there are exactly N different pairs (i, j) that denotes a palindrome.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the sought number of pairs that denote palindrome.
Output
For each test case, output a single line containing a string S, consisting of lowecase Latin letters, and having exactly N distinct palindromedenoting pairs. If there's a few such strings, output any one.
If such string S doesn't exist, output 1 instead of it.
Constraints
 1 ≤ T ≤ 100
 1 ≤ N ≤ 10^{4}
Example
Input: 3 6 7 2 Output: noon radar ab
Explanation
Example case 1. In the string "noon", the pairs that denote a palindrome are (1indexed): (1, 1), (1, 4), (2, 2), (2, 3), (3, 3), (4, 4).
Example case 2. In the string "radar", the pairs that denote a palindrome are (1indexed): (1, 1), (1, 5), (2, 2), (2, 4), (3, 3), (4, 4), (5, 5).
Example case 3. In the string "ab", the pairs denoting a palindrome are : (1, 1), (2, 2)
Author:  xcwgf666 
Tester:  
Editorial  http://discuss.codechef.com/problems/NDIFFPAL 
Tags  adhoc dynamicprogramming easy palindrome snckpa16 strings xcwgf666 
Date Added:  31052016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 