C. Almost All Multiples

Given two integers $n$ and $x$, a permutation$^{\dagger}$ $p$ of length $n$ is called funny if $p_i$ is a multiple of $i$ for all $1 \leq i \leq n - 1$, $p_n = 1$, and $p_1 = x$.

Find the lexicographically minimal$^{\ddagger}$ funny permutation, or report that no such permutation exists.

$^{\dagger}$ A permutation of length $n$ is an array consisting of each of the integers from $1$ to $n$ exactly once.

$^{\ddagger}$ Let $a$ and $b$ be permutations of length $n$. Then $a$ is lexicographically smaller than $b$ if in the first position $i$ where $a$ and $b$ differ, $a_i < b_i$. A permutation is lexicographically minimal if it is lexicographically smaller than all other permutations.

Input

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers $n$ and $x$ ($2 \leq n \leq 2 \cdot 10^5$; $1 < x \leq n$).

The sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, if the answer exists, output $n$ distinct integers $p_1, p_2, \dots, p_n$ ($1 \leq p_i \leq n$) — the lexicographically minimal funny permutation $p$. Otherwise, output $-1$.

Example

input

3
3 3
4 2
5 4

output

3 2 1 
2 4 3 1 
-1

Note

In the first test case, the permutation $[3,2,1]$ satisfies all the conditions: $p_1=3$, $p_3=1$, and:

$p_1=3$ is a multiple of $1$.
$p_2=2$ is a multiple of $2$.
In the second test case, the permutation $[2,4,3,1]$ satisfies all the conditions: $p_1=2$, $p_4=1$, and:

$p_1=2$ is a multiple of $1$.
$p_2=4$ is a multiple of $2$.
$p_3=3$ is a multiple of $3$.
We can show that these permutations are lexicographically minimal.

No such permutations exist in the third test case.

解题思路

　　首先序列$a = \{ {1, 2, \ldots, n} \}$（即$a_i = i$）是满足条件的，现在交换一下$a_1$和$a_n$，那么序列就变成了$a = \{ {n, 2, 3, \ldots, n-1, 1} \}$，也是满足条件的。当我们选择下标$x$，交换$a_1$和$a_x$（也就是把$n$换到了下标$x$的位置），这时如果有$n \mid x$，那么得到的序列还是满足条件的（不一定是字典序最小）。如果$n \nmid x$，那么我们要往后找到一个$x$的倍数放到$x$这个位置，这个数可以是$k \cdot x$ $(2 \leq k \leq \left\lfloor {\frac{n}{x}} \right\rfloor)$，同理，如果选择了$k \cdot x$，那么还需要往后找到一个$k \cdot x$的倍数放到$k \cdot x$这个位置，以此类推，最终要把$n$放到某个位置，由于最后这个位置也是$x$的倍数，又因为这个位置不能整除$n$，因此无解。

　　对于有解的情况为了得到字典序最小，我们可以先让$a_x = n$，然后往后遍历找$x$的第一个倍数（也就是$2 \cdot x$），然后交换$a_{x}$和$a_{2x}$，此时我们应该往后找到$2 \cdot x$的第一个倍数（也就是$4 \cdot x$），然后交换交换$a_{2x}$和$a_{4x}$，以此类推，直到无法交换为止。

　　AC代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 2e5 + 10;
 5 
 6 int a[N];
 7 
 8 void solve() {
 9     int n, m;
10     scanf("%d %d", &n, &m);
11     if (n % m) {
12         printf("-1\n");
13         return;
14     }
15     a[1] = m, a[n] = 1;
16     for (int i = 2; i < n; i++) {
17         a[i] = i;
18     }
19     if (n != m) a[m] = n;    // 如果a[1]=n那么已经是字典序最小了
20     for (int i = m + m, j = m; i < n; i += j) {    // 当前放n的位置为j，因此要找j的倍数，即i+=j
21         if (n % i == 0) {    // n可以放到i这个位置
22             swap(a[i], a[j]);
23             j = i;
24         }
25     }
26     for (int i = 1; i <= n; i++) {
27         printf("%d ", a[i]);
28     }
29     printf("\n");
30 }
31 
32 int main() {
33     int t;
34     scanf("%d", &t);
35     while (t--) {
36         solve();
37     }
38     
39     return 0;
40 }

参考资料

　　Codeforces Round #836 (Div. 2) Editorial：https://codeforces.com/blog/entry/109438