Background

⚡Surpass all and shock mortals.⚡

⚡Bring the final divine descent of machinery.⚡

⚡The power of the storm fills the whole body.⚡

⚡The last strike, core resonance.⚡

Problem Description

Given positive integers $p$ and $n$. For a permutation, we say that two adjacent elements produce "resonance" if and only if the sum of these two numbers is a multiple of $p$.

Please construct a permutation of $1 \sim n$ to maximize the number of "resonances" that occur. If there are multiple solutions, output any one.

Input Format

This problem has multiple test cases.

The first line of input contains a positive integer $T$, representing the number of test cases.

For each test case, the input contains one line with two positive integers $n$ and $p$ separated by spaces.

Output Format

For each test case, output one line containing $n$ positive integers separated by spaces, representing the permutation you constructed.

3
9 1
5 2
1 12345

3 8 7 1 4 5 6 9 2
1 5 3 2 4
1

Hint

This problem uses bundled tests.

• Subtask 0 (15 pts): $n \leq 9$, $T \le 10$.
• Subtask 1 (10 pts): $p = 2$.
• Subtask 2 (30 pts): $p = 3$.
• Subtask 3 (45 pts): No special constraints.

Constraints: For all testdata, $1 \leq n \leq 10^5$, $1 \leq p \leq 10^8$, $1 \leq T \leq 10^4$, and $1 \leq \sum n \leq 3\times 10^5$.

Translated by ChatGPT 5