UOJ Logo Universal Online Judge

UOJ

#343. 【清华集训2017】避难所

附件下载 统计

题目背景

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

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

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

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

题目描述

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

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

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

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

我们可以从b-1到2试除,直到p为1为止,答案是389,可以验证389是满足$p = F(n, b)$最小的$n$。

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

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

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

输入格式

从标准输入读入数据。

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

接下来每行一个整数b,表示进制。

输出格式

输出到标准输出。

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

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

样例一

input

3
8
9
10

output

-1
3 6 6 6
-1

提示

别紧张,你这样没事。

限制与约定

对于第 $1$ 个测试点,分值为 $30$,$1 \leq n \leq 32$;

对于第 $2$ 个测试点,分值为 $40$,$1 \leq n \leq 100$;

对于第 $3$ 个测试点,分值为 $30$,$1 \leq t \leq 200, 1 \leq n \leq 100000$。

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载