Little Z is a girl who loves programming. One day, while working on a programming problem, she accidentally discovered a magical integer $142857$. $142857 \times 2 = 285714$, and all the digits of $285714$ are exactly a permutation of the digits of $142857$. She was curious if there were any larger integers that satisfy this property. She wrote a search program and found some larger interesting numbers: $26835741 \times 2 = 53671482$ $0987312654 \times 2 = 1974625308$ ... She was not satisfied with solving such problems in base $10$, so she wanted to know if, for a given 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 \le i \le n$, the $i$-th digits of $x$ and $2x$ in base $B$ cannot both be $0$.

Input

The input contains multiple test cases. The first line contains a positive integer $T$, representing the number of test cases. The next $T$ lines each contain two positive integers $n$ and $B$, representing the $i$-th test case.

Output

For each test case, output a single line. If the test case has a solution, output $n$ non-negative integers in order from the most significant digit to the least significant digit, representing the value of your answer in base $B$. Otherwise, simply output $-1$.

Examples

Input 1

3
6 10
3 3
6 7

Output 1

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

Note 1

The explanation for the first test case can be found in the problem description. For the second test case, one can show that no such positive integer exists by enumerating all $n$-digit numbers in base $B$. For the third test case, the base $7$ representation of $2x$ is $103635_{(7)}$, so this is a valid answer. Note that the answer files for these examples only indicate one possible valid answer and do not imply that the answer file corresponds exactly to the output of the standard program.

Examples 2

(See double/double2.in)

Output 2

(See double/double2.ans)

Note 2

This test case satisfies the constraints of test point 3. Note that the answer file for this example only indicates one possible valid answer and does not imply that the answer file corresponds exactly to the output of the standard program.

Examples 3

(See double/double3.in)

Output 3

(See double/double3.ans)

Note 3

This test case satisfies the constraints of test point 17. Note that the answer file for this example only indicates one possible valid answer and does not imply that the answer file corresponds exactly to the output of the standard program.

Note

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++14 After compiling to the executable checker, you can test your answer in the following ways: checker <input> <output> <answer>: Uses the double*.ans files in the contestant directory to verify the correctness of your answer for the sample test points double*.in. checker <input> <output> <output>: Checks if your output for this test case meets the problem requirements. Note that when testing in this way, an output of "no solution" will always be reported as valid. Contestants should pay attention to clearing data between multiple test cases.

Constraints

For all data, $1 \le T \le 10^4$, $2 \le \sum B \le 2 \times 10^5$, $1 \le \sum n \le 2 \times 10^5$, $n \ge 1$, $B \ge 2$. The specific data scale and constraints are shown in the table below.