408492: GYM103150 F Palindromicity

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Palindromicitytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given an integer $$$n$$$. Output any string of lowercase English letters with length at most $$$300$$$ that has exactly $$$n$$$ palindromic substrings.

Recall that $$$p$$$ is a substring of $$$q$$$ if $$$p$$$ can be obtained by removing several characters (possibly none) from the beginning and from the end of $$$q$$$. Also recall that a palindrome is a string that reads the same backwards as forwards. For example, aba and o are palindromes, but ab and aaba are not.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^3$$$) — the number of test cases.

The only line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^4$$$).

Output

For each test case, output one string of lowercase English letters with length at most $$$300$$$ that has exactly $$$n$$$ palindromic substrings.

We have a proof that, under the given constraints, such a string always exists.

ExampleInput
6
1
11
12
13
21
25
Output
o
kannawoah
abacaba
feelssadman
howtomakegoodsamples
anutforajaroftuna

加入题单

上一题 下一题 算法标签: