P9573 "TAOI-2" Core Resonance

⚡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.⚡

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.

**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.

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

**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