github.com/captn3m0/codechef.git

---
category_name: easy
problem_code: NDIFFPAL
problem_name: 'N different palindromes'
languages_supported:
    - 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
max_timelimit: '1'
source_sizelimit: '50000'
problem_author: xcwgf666
problem_tester: 'kevinsogo,antoniuk1'
date_added: 31-05-2016
tags:
    - ad
    - dynamic
    - easy
    - palindrome
    - snckpa16
    - strings
    - xcwgf666
editorial_url: 'http://discuss.codechef.com/problems/NDIFFPAL'
time:
    view_start_date: 1465140600
    submit_start_date: 1465140600
    visible_start_date: 1465140600
    end_date: 1735669800
    current: 1493558171
layout: problem
---
All submissions for this problem are available.###  Read problems statements in [Mandarin Chinese](http://www.codechef.com/download/translated/SNCKPA16/mandarin/NDIFFPAL.pdf), [Russian](http://www.codechef.com/download/translated/SNCKPA16/russian/NDIFFPAL.pdf) and [Vietnamese](http://www.codechef.com/download/translated/SNCKPA16/vietnamese/NDIFFPAL.pdf) 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 **i**-th character and ending at the **j**-th 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 palindrome-denoting 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** ≤ **104**

### Example

<pre><b>Input:</b>
<tt>3
6
7
2
</tt>
<b>Output:</b>
<tt>noon
radar
ab</tt>
</pre>### Explanation

**Example case 1.** In the string "noon", the pairs that denote a palindrome are (1-indexed): **(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 (1-indexed): **(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)**