Row Major
Contest: Codeforces Round 884 (Div. 1 + Div. 2)
Difficulty rating: 1400
Tags: constructive algorithms, greedy, math, number theory, strings

The row-major order of an $$$r \times c$$$ grid of characters $$$A$$$ is the string obtained by concatenating all the rows, i.e. $$$$$$ A_{11}A_{12} \dots A_{1c}A_{21}A_{22} \dots A_{2c} \dots A_{r1}A_{r2} \dots A_{rc}. $$$$$$

A grid of characters $$$A$$$ is bad if there are some two adjacent cells (cells sharing an edge) with the same character.

You are given a positive integer $$$n$$$. Consider all strings $$$s$$$ consisting of only lowercase Latin letters such that they are not the row-major order of any bad grid. Find any string with the minimum number of distinct characters among all such strings of length $$$n$$$.

It can be proven that at least one such string exists under the constraints of the problem.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

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

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, output a string with the minimum number of distinct characters among all suitable strings of length $$$n$$$.

If there are multiple solutions, print any of them.

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

Note:
In the first test case, there are $$$3$$$ ways $$$s$$$ can be the row-major order of a grid, and they are all not bad: tththathatat It can be proven that $$$3$$$ distinct characters is the minimum possible.

In the second test case, there are $$$2$$$ ways $$$s$$$ can be the row-major order of a grid, and they are both not bad: iiss It can be proven that $$$2$$$ distinct characters is the minimum possible.

In the third test case, there is only $$$1$$$ way $$$s$$$ can be the row-major order of a grid, and it is not bad.

In the fourth test case, there are $$$4$$$ ways $$$s$$$ can be the row-major order of a grid, and they are all not bad: ttotomtomatoomaatomtoato It can be proven that $$$4$$$ distinct characters is the minimum possible. Note that, for example, the string "orange" is not an acceptable output because it has $$$6 > 4$$$ distinct characters, and the string "banana" is not an acceptable output because it is the row-major order of the following bad grid: banana

Example input:
4
4
2
1
6

Example output:
that
is
a
tomato

Editorial:
The condition is equivalent to a graph of pairs of characters in $$$s$$$ that need to be different. In graph-theoretic language, we need to find the chromatic number of this graph.
By considering the $$$1 \times n$$$ and $$$n \times 1$$$ grids, there is an edge between character $$$u$$$ and $$$u+1$$$ for all $$$1 \le u \le n-1$$$. By considering a $$$\frac{n}{d} \times d$$$ grid (where $$$d$$$ divides $$$n$$$), there is an edge between character $$$u$$$ and $$$u+d$$$ for all $$$1 \le u \le n-d$$$ whenever $$$d$$$ divides $$$n$$$.
Let $$$c$$$ be the smallest positive integer that does not divide $$$n$$$. There is an edge between every pair of the characters $$$1,\dots,c$$$ (in graph-theoretic language, this is a clique), so the answer is at least $$$c$$$. On the other hand, consider the string obtained by letting $$$s_1,\dots,s_c$$$ be all distinct characters and repeating this pattern periodically ($$$s_i = s_{i+c}$$$ for all $$$1 \le i \le n-c$$$). Any pair of equal characters have an index difference that is a multiple of $$$c$$$, say $$$kc$$$. But since $$$c$$$ does not divide $$$n$$$, $$$kc$$$ also does not divide $$$n$$$, so these characters are not connected by an edge. Therefore this construction gives a suitable string with $$$c$$$ distinct characters.
The time complexity is $$$\mathcal{O}(n)$$$.