Shohag Loves Mod
Contest: CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 800
Tags: constructive algorithms, number theory

Shohag has an integer $$$n$$$. Please help him find an increasing integer sequence $$$1 \le a_1 \lt a_2 \lt \ldots \lt a_n \le 100$$$ such that $$$a_i \bmod i \neq a_j \bmod j$$$ $$$^{\text{∗}}$$$ is satisfied over all pairs $$$1 \le i \lt j \le n$$$.

It can be shown that such a sequence always exists under the given constraints.

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

The first and only line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 50$$$).

Output format:
For each test case, print $$$n$$$ integers — the integer sequence that satisfies the conditions mentioned in the statement. If there are multiple such sequences, output any.

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

Note:
In the first test case, the sequence is increasing, values are from $$$1$$$ to $$$100$$$ and each pair of indices satisfies the condition mentioned in the statement:

- For pair $$$(1, 2)$$$, $$$a_1 \bmod 1 = 2 \bmod 1 = 0$$$, and $$$a_2 \bmod 2 = 7 \bmod 2 = 1$$$. So they are different.
- For pair $$$(1, 3)$$$, $$$a_1 \bmod 1 = 2 \bmod 1 = 0$$$, and $$$a_3 \bmod 3 = 8 \bmod 3 = 2$$$. So they are different.
- For pair $$$(2, 3)$$$, $$$a_2 \bmod 2 = 7 \bmod 2 = 1$$$, and $$$a_3 \bmod 3 = 8 \bmod 3 = 2$$$. So they are different.

Note that you do not necessarily have to print the exact same sequence, you can print any other sequence as long as it satisfies the necessary conditions.

Example input:
2
3
6

Example output:
2 7 8
2 3 32 35 69 95

Editorial:
THOUGHT: A general approach to tackle ad-hoc problems is to play around with the conditions and see if we can add more constraints to limit the search space.
ACTION: Let's analyze the modular condition $$$a_i \bmod i$$$.
We know that $$$a_i \bmod i < i$$$, and all $$$a_i \bmod i$$$ values are distinct. Let's explore this step by step:
• $$$a_1 \bmod 1$$$ is always $$$0$$$.
• $$$a_2 \bmod 2$$$ can be $$$0$$$ or $$$1$$$. But since all $$$a_i \bmod i$$$ values must be distinct, $$$a_2 \bmod 2$$$ must be $$$1$$$ (otherwise, it would equal $$$a_1 \bmod 1$$$).
• $$$a_3 \bmod 3$$$ can be $$$0$$$, $$$1$$$, or $$$2$$$. Similarly, $$$a_3 \bmod 3$$$ must be $$$2$$$ (to avoid duplication with $$$a_1 \bmod 1$$$ or $$$a_2 \bmod 2$$$).
• $$$\ldots$$$
• $$$a_n \bmod n$$$ must be $$$n-1$$$.
OBSERVATION: This leads to the constraint $$$a_i \bmod i = i - 1$$$.
THOUGHT: Next, let's consider the increasing sequence condition.
OBSERVATION: Since the sequence must be increasing, we add the constraint $$$a_i \ge i$$$.
THOUGHT: To further limit the search space, note that $$$n$$$ can be up to $$$50$$$, and $$$a_i$$$ must be $$$\le 100$$$.
OBSERVATION: This suggests that we can restrict $$$a_i$$$ to values up to $$$2 \cdot n$$$.
THOUGHT: Let's compile the constraints:
1. $$$a_i \bmod i = i - 1$$$.
2. $$$a_i \ge i$$$.
3. $$$a_i \le 2 \cdot n$$$.
Now we need to build the sequence that satisfies these conditions.
ACTION: Let's build the sequence starting from the end.
• $$$a_n \bmod n = n-1$$$. Thus, $$$a_n$$$ can be $$$n-1$$$ or $$$2 \cdot n - 1$$$. Since $$$a_n \ge n$$$, $$$a_n$$$ must be $$$2 \cdot n - 1$$$.
• $$$a_{n-1} \bmod (n-1) = n-2$$$. So $$$a_{n-1}$$$ can be $$$n-2$$$ or $$$(n - 2) + (n - 1) = 2 \cdot n - 3$$$. Since $$$a_{n-1} \ge n-1$$$, $$$a_{n-1}$$$ must be $$$2 \cdot n - 3$$$.
• $$$\ldots$$$
• $$$a_i \bmod i = i - 1$$$. Thus, $$$a_i$$$ can be $$$i - 1$$$ or $$$2 \cdot i - 1$$$ or $$$3 \cdot i - 1 \ldots$$$. Since $$$a_i \ge i$$$ and the odd numbers greater than $$$2 \cdot i$$$ have already been used, $$$a_i$$$ must be $$$2 \cdot i - 1$$$.
OBSERVATION: If we limit the elements to $$$2 \cdot n$$$, there is exactly one sequence that satisfies all conditions.
CONCLUSION: The sequence is $$$a_i = 2 \cdot i - 1$$$, which is $$$1, 3, 5, \ldots, 2 \cdot n - 1$$$.
VALIDATION: We can validate the solution by checking if it satisfies all the constraints. $$$a_i \bmod i = (2 \cdot i - 1) \bmod i = i - 1$$$. So all $$$a_i \bmod i$$$ are distinct and values are under $$$2 \cdot n$$$. So the sequence is valid.
Time Complexity: $$$\mathcal{O}(n)$$$.