408492: GYM103150 F Palindromicity

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.

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$$$).

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.

6
1
11
12
13
21
25

o
kannawoah
abacaba
feelssadman
howtomakegoodsamples
anutforajaroftuna