Problem Description

Xiao Z is a girl who loves programming.

One day, while working on a programming problem, she stumbled upon a magical integer, $142857$.

She noticed that $142857 \times 2 = 285714$, and all the digits of $285714$ are exactly a permutation of the digits of $142857$.

Curious, she wondered if there are larger integers with this property.

She wrote a search program and found some larger interesting numbers:

$26835741 \times 2 = 53671482$

$0987312654 \times 2 = 1974625308$

$\dots$

Not content with solving this problem in decimal, she wants to know if there exists an $n$-digit positive integer $x$ in base $B$ such that all the digits of $2x$ in base $B$ are a permutation of the digits of $x$.

Since she dislikes the digit $0$, she also requires that for any $1 \leq i \leq n$, neither $x$ nor $2x$ has the digit $0$ at the $i$-th position in base $B$.

Input Format

The input contains multiple test cases.

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

The next $T$ lines, each containing two positive integers $n$ and $B$, represent the $i$-th test case.

Output Format

For each test case, output one line.

If the test case has a solution, output $n$ non-negative integers in descending order, representing the answer in base $B$.

Otherwise, output a single number $-1$.

Sample Input and Output

Sample Input #1

3
6 10
3 3
6 7

Sample Output #1

1 4 2 8 5 7
-1
0 3 5 3 1 6

Sample Input #2

Sample 2 is in the attached file double2.in
This set of data meets the constraints of test point 3.

Sample Output #2

Sample 2 is in the attached file double2.ans

Sample Input #3

Sample 3 is in the attached file double3.in
This set of data meets the constraints of test point 17.

Sample Output #3

Sample 3 is in the attached file double3.ans

Notes/Hints

[Sample 1 Explanation]

• The explanation for the first set of data is in the [Problem Description].
• For the second set of data, it can be shown through enumeration of all $n$-digit $B$-ary numbers that no such positive integer exists.
• For the third set of data, $2x$ in base $7$ is represented as $103635_{(7)}$, which is a valid answer.

Note that the answer files for the samples only indicate one possible valid answer and do not necessarily correspond exactly to the output of the standard program.

[Sample 2/3 Explanation]

Note that the answer files for the samples only indicate one possible valid answer and do not necessarily correspond exactly to the output of the standard program.

[Hints]

Since the answer may not be unique, we have provided a checker checker.cpp and a library file testlib.h.

You can compile checker.cpp using the following command:

g++ -o checker checker.cpp -O2 -std=c++11

After compiling checker.cpp to produce the executable checker, you can test your answers using the following methods:

checker <input> <output> <answer>: Use the answer files in the player directory double/double*.ans to verify the correctness of your answers for the sample test points double/double*.in.

checker <input> <output> <output>: This will check if all your solutions reported as having a solution meet the requirements of the problem. Note that this method will always report no solution as valid, as it only checks the solutions you report.

Please be aware of the clearing issue between multiple test cases.

[Data Size and Constraints]

For all data, $1 \leq T \leq 10^4$, $2 \leq \sum B \leq 2 \times 10^5$, $1 \leq \sum n \leq 2 \times 10^5$, $n \geq 1$, $B \geq 2$.

Specific data sizes and constraints are detailed in the table below.

见题面 Input 部分

见题面 Output 部分