310509: CF1844D. Row Major

D. Row Majortime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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.

ExampleInput

4
4
2
1
6

Output

that
is
a
tomato

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:

t		t	h		t	h	a	t
h		a	t
a
t

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:

i		i	s
s

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:

t

t

o

t

o

m

t

o

m

a

t

o

o

m

a

a

t

o

m

t

o

a

t

o

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:

b	a
n	a
n	a

题目大意：

给定一个由小写拉丁字母组成的字符串s，如果s不是任何“坏网格”的行主序，则称s是“好的”。一个“坏网格”是指存在两个相邻（共享边缘）的单元格具有相同字符的网格。你需要找到长度为n的字符串s，使得s的不同字符数量在所有这样的字符串中是最小的。

输入数据格式：

每个测试用例包含多个测试案例。第一行包含测试案例的数量t（1 ≤ t ≤ 10^4）。接下来的每一行包含一个整数n（1 ≤ n ≤ 10^6），表示每个测试案例的字符串长度。所有测试案例的n之和不超过10^6。

输出数据格式：

对于每个测试案例，输出一个长度为n的字符串，该字符串的不同字符数量在所有合适的字符串中是最小的。如果有多个解，输出其中任何一个。

示例：

输入：
```
4
4
2
1
6
```
输出：
```
that
is
a
tomato
```

注意：

- 在第一个测试案例中，有3种方式s可以是网格的行主序，它们都是好的。
- 在第二个测试案例中，有2种方式s可以是网格的行主序，它们都是好的。
- 在第三个测试案例中，只有1种方式s可以是网格的行主序，它是好的。
- 在第四个测试案例中，有4种方式s可以是网格的行主序，它们都是好的。题目大意： 给定一个由小写拉丁字母组成的字符串s，如果s不是任何“坏网格”的行主序，则称s是“好的”。一个“坏网格”是指存在两个相邻（共享边缘）的单元格具有相同字符的网格。你需要找到长度为n的字符串s，使得s的不同字符数量在所有这样的字符串中是最小的。 输入数据格式： 每个测试用例包含多个测试案例。第一行包含测试案例的数量t（1 ≤ t ≤ 10^4）。接下来的每一行包含一个整数n（1 ≤ n ≤ 10^6），表示每个测试案例的字符串长度。所有测试案例的n之和不超过10^6。 输出数据格式： 对于每个测试案例，输出一个长度为n的字符串，该字符串的不同字符数量在所有合适的字符串中是最小的。如果有多个解，输出其中任何一个。 示例： 输入： ``` 4 4 2 1 6 ``` 输出： ``` that is a tomato ``` 注意： - 在第一个测试案例中，有3种方式s可以是网格的行主序，它们都是好的。 - 在第二个测试案例中，有2种方式s可以是网格的行主序，它们都是好的。 - 在第三个测试案例中，只有1种方式s可以是网格的行主序，它是好的。 - 在第四个测试案例中，有4种方式s可以是网格的行主序，它们都是好的。