codeforces#P1758C. Almost All Multiples

Almost All Multiples

Description

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.

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

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

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

3
3 3
4 2
5 4
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.