Problem Description

Xiao Z is a girl who likes programming.

One day, while solving a programming problem, she accidentally found a magical integer $142857$.

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

She was curious whether there exists a larger integer with this property.

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

$26835741 \times 2 = 53671482$

$0987312654 \times 2 = 1974625308$

$\dots$

She is not satisfied with only the decimal case. So she wants to know whether, in base $B$, there exists an $n$-digit positive integer $x$ such that all digits of $2x$ in base $B$ are a permutation of all digits of $x$ in base $B$.

Since she hates the digit $0$, she also requires that for any $1 \leq i \leq n$, the $i$-th digit of $x$ and the $i$-th digit of $2x$ in base $B$ cannot both be $0$ at the same time.

Input Format

The input contains multiple test cases.

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

The next $T$ lines each contain two positive integers $n$ and $B$, describing one test case.

Output Format

For each test case, output one line.

If there is a solution for this test case, output $n$ non-negative integers from the most significant digit to the least significant digit, representing the value of your answer in base $B$.

Otherwise, output a single number $-1$.

3
6 10
3 3
6 7

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

样例 2 见附件 double2.in
本组数据满足测试点 3 的限制。

样例 2 见附件 double2.ans

样例 3 见附件 double3.in
本组数据满足测试点 17 的限制。

样例 3 见附件 double3.ans

Hint

[Sample 1 Explanation]

• The explanation of the first test case can be found in the Description.
• For the second test case, you can prove that such a positive integer cannot be found by enumerating all $n$-digit base-$B$ numbers.
• For the third test case, the base-$7$ representation of $2x$ is $103635_{(7)}$, so this is a valid answer.

Note that the sample output only shows one possible valid answer, and it does not mean the sample output must exactly match the output of the standard solution.

[Sample 2/3 Explanation]

Note that the sample output only shows one possible valid answer, and it does not mean the sample output must exactly match the output of the standard solution.

[Hint]

Since the answer may not be unique, we provide 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 into an executable file checker, you can test your output as follows:

checker <input> <output> <answer>: the files double/double*.ans under the contestant directory can be used to verify the correctness of your output on the sample test points double/double*.in.

checker <input> <output> <output>: it will check whether all outputs you claim to have solutions satisfy the problem requirements. Note that in this testing mode, reporting no solution will always be judged as valid, because in this mode we only check all solutions you output.

Please pay attention to clearing data structures between multiple test cases.

[Constraints and Conventions]

For all testdata, $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$.

The detailed constraints are shown in the table below.

Translated by ChatGPT 5