题目描述

小 Z 是一个喜欢编程的女孩子。

这天，她在做一道编程题的时候偶然发现了一个神奇的整数 $142857$。

$142857 \times 2 = 285714$，而 $285714$ 的所有数位恰好是 $142857$ 的一个排列。

她很好奇，有没有更大的满足这种性质的整数。

她写了一个搜索，发现了一些更大的有趣的数：

$26835741 \times 2 = 53671482$

$0987312654 \times 2 = 1974625308$

$\dots$

她不满足于解决十进制下这样的问题，于是她想知道，是否在 $B$ 进制下存在一个 $n$ 位正整数 $x$，满足 $2x$ 的所有数位在 $B$ 进制下是 $x$ 的所有数位的一个排列。

由于她讨厌数字 $0$，因此她还要求对于任意 $1 \leq i \leq n$，$x$ 和 $2x$ 在 $B$ 进制下的第 $i$ 位不能同时为 $0$。

输入格式

输入包含多组数据。

输入的第一行是一个正整数 $T$，表示数据组数。

接下来 $T$ 行，第 $i$ 行包含两个正整数 $n$ 和 $B$，表示第 $i$ 组数据。

输出格式

对于每组数据，输出一行。

若本组数据有解，按照从高位到低位的顺序输出 $n$ 个非负整数，表示你找到的答案在 $B$ 进制下的值。

否则只需要输出一个数 $-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

提示

【样例 1 解释】

• 第一组数据的解释参见【题目描述】。
• 对于第二组数据，可以通过枚举所有的 $n$ 位 $B$ 进制数说明一定不能找到这样的正整数。
• 对于第三组数据，$2x$ 的 $7$ 进制表示为 $103635_{(7)}$，因此这是一个满足题意的答案。

注意此样例的答案文件仅表明了一种可能的合法答案，不表明答案文件恰好对应标准程序的输出。

【样例 2/3 解释】

注意此样例的答案文件仅表明了一种可能的合法答案，不表明答案文件恰好对应标准程序的输出。

【提示】

由于答案可能不唯一，我们下发了校验器 checker.cpp 和库文件 testlib.h。

可以使用以下命令编译 checker.cpp：

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

将 checker.cpp 编译得到可执行文件 checker 后你可以使用以下方式测试你的答案：

checker <input> <output> <answer>：利用选手目录下的 double/double*.ans 可以用来检验你的答案在样例测试点 double/double*.in 的正确性。

checker <input> <output> <output>：会检查你的所有有解输出是否符合题目要求。注意以此种方式测试的时候，输出无解总会被报告为合法，因为在此种运行方式下我们只会检查你报告的所有解。

请选手注意多组数据之间的清空问题。

【数据规模与约定】

对于全部数据，$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$。

具体的数据规模与约定见下表。

测试点编号	$n \leq$	$B \leq$	$T \leq$	特殊约定
$1$	$8$	$8$	$10$
$2$			$10^4$
$3$	$2 \times 10^5$		$10$
$4$			$10^4$
$5$
$6$	$15$		$100$
$7$	$40$
$8$	$100$
$9$	$300$
$10$	$1000$
$11$	$3000$
$12$	$15000$
$13$	$50000$
$14$	$2 \times 10^5$
$15$	$200$		$10^4$	$n \geq 100$
$16$	$5000$
$17$	$2 \times 10^5$
$18$	$300$			$B=3k-1,k \in \N^*$
$19$	$2 \times 10^5$
$20$	$300$			$B=3k,k \in \N^*$
$21$	$2 \times 10^5$
$22$	$100$
$23$	$500$	$5000$
$24$	$2 \times 10^5$
$25$