#P6562. 「清华集训 2017」避难所

「清华集训 2017」避难所

「清华集训 2017」避难所

题目描述

“B君啊,你当年的伙伴都不在北京了,为什么你还在北京呢?”

“大概是因为出了一些事故吧,否则这道题就不叫避难所了。”

“唔,那你之后会去哪呢?”

“去一个没有冬天的地方。”

对于一个正整数 nn,我们定义他在 bb 进制下,各个位上的数的乘积为 p=F(n,b)p = F(n, b)。

比如 F(3338,10)=216F(3338, 10) = 216。

考虑这样一个问题,已知 pp 和 bb,求最小的 nn 满足 p=F(n,b)p = F(n, b)。

这是一个非常有趣的问题,对于一些 bb 来说,我们可以贪心来做,比如如果 b=10,p=216b=10, p=216。

我们可以依次用 b−1,b−2,…,2b-1,b-2,\ldots,2 试除:对每个数,只要它能整除当前的 pp 就除以它,并记录它。最后将记录的数字从小到大排列,作为从高位到低位的各位数字,答案是 389389,可以验证 389389 是满足 p=F(n,b)p = F(n, b) 最小的 nn。

但是对于一些进制 bb,是不能用贪心做的,比如 b=9,p=216b = 9, p = 216。使用贪心得到的解是 33383338,而最优解是 666666。(均为 99 进制下的。)

本题便是在给定进制 bb 的情况下,举出一个这样的反例,或指出这样的反例不存在。

由于计算资源所限,反例中所有数字的乘积不能超过 101810^{18}。如果最小的反例中所有数字的乘积超过了 101810^{18},那么也应该输出 −1-1。

输出的各位数字均以十进制整数表示,但它们共同组成一个 bb 进制数,按从最高位到最低位的顺序给出。反例针对相同的正乘积 pp:贪心得到的数必须严格大于真正的最小解。数值比较先比较位数,位数相同时再比较从高位到低位的字典序。无需寻找乘积最小的反例,只需给出任意一个满足乘积上限的反例的最优解。

输入格式

从标准输入读入数据。

第一行一个整数 tt,表示一共有 tt 组数据。

接下来 tt 行,每行一个整数 bb,表示通常意义下的整数进制,b≥2b\geq2。

输出格式

输出到标准输出。

如果不存在反例,输出一行一个整数 −1-1。

如果存在反例,首先输出一个整数 kk,表示反例 nn 的位数,接下来在同一行输出 kk 个十进制整数,表示任意一个反例的最优解。

样例输入 1

3
8
9
10

样例输出 1

-1
3 6 6 6
-1

数据范围与提示

对于第 11 个测试点,分值为 3030,2≤b≤322\leq b\leq32;

对于第 22 个测试点,分值为 4040,2≤b≤1002\leq b\leq100;

对于第 33 个测试点,分值为 3030,1≤t≤200,2≤b≤1000001 \leq t \leq 200, 2 \leq b \leq 100000。