Diane
Contest: Codeforces Round 735 (Div. 2)
Difficulty rating: 1800
Tags: constructive algorithms, greedy, strings

You are given an integer $$$n$$$. Find any string $$$s$$$ of length $$$n$$$ consisting only of English lowercase letters such that each non-empty substring of $$$s$$$ occurs in $$$s$$$ an odd number of times. If there are multiple such strings, output any. It can be shown that such string always exists under the given constraints.

A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, print a single line containing the string $$$s$$$. If there are multiple such strings, output any. It can be shown that such string always exists under the given constraints.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, each substring of "abc" occurs exactly once.

In the third test case, each substring of "bbcaabbba" occurs an odd number of times. In particular, "b" occurs $$$5$$$ times, "a" and "bb" occur $$$3$$$ times each, and each of the remaining substrings occurs exactly once.

Example input:
4
3
5
9
19

Example output:
abc
diane
bbcaabbba
youarethecutestuwuu

Editorial:
Consider the strings of type "$$$aa \ldots a$$$". Which substring occurs in which parity? Observe. Play with them.
Consider the string "$$$aa \ldots a$$$" ($$$k$$$ times '$$$a$$$'). WLOG Let $$$k$$$ be an odd integer. In this string "$$$a$$$" occurs $$$k$$$ times, "$$$aa$$$" occurs $$$k - 1$$$ times and so on. So "$$$a$$$", "$$$aa$$$", "$$$aaa$$$", $$$\ldots$$$ occurs odd, even, odd, even, $$$\ldots$$$ times, respectively.
Now let's look at the string "$$$aa \ldots a$$$" ($$$k - 1$$$ times '$$$a$$$'). In this string, "$$$a$$$", "$$$aa$$$", "$$$aaa$$$", $$$\ldots$$$ occurs even, odd, even, odd, $$$\ldots$$$ times, respectively. What can be done now?
Did you know that odd $$$+$$$ even $$$=$$$ odd?
Pause and think.
Let's merge both strings! If we merge them with "$$$b$$$" in-between i.e. "$$$\underbrace{aaa \ldots aaa}_\text{k times} b \underbrace{aaa\ldots aa}_\text{k - 1 times}$$$", then each substring will occur an odd number of times. Thats because each of "$$$a$$$", "$$$aa$$$", "$$$aaa$$$", $$$\ldots$$$ occurs odd $$$+$$$ even $$$=$$$ odd times, and each newly created substring occurs exactly once.
What will happen if we set $$$k = \left \lfloor{\frac{n}{2}}\right \rfloor$$$?
So here is the solution to the problem: "$$$\underbrace{aaa \ldots aaa}_\text{k times} + b | bc + \underbrace{aaa\ldots aa}_\text{k- 1 times}$$$", where $$$k = \left \lfloor{\frac{n}{2}}\right \rfloor$$$ and "$$$b$$$" when $$$n$$$ is even and "$$$bc$$$" when $$$n$$$ is odd. For example, if $$$n = 6$$$, answer is "$$$aaabaa$$$" and if $$$n = 7$$$, answer is "$$$aaabcaa$$$".
Time Complexity: $$$\mathcal{O}(n)$$$