#2009. 避难所

    ID: 2009 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest488来源:qoj.ac数据:公开样例贪心枚举

避难所

避难所

题目描述

标题: 避难所 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

“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 的情况下,举出一个这样的反例,或指出这样的反例不存在。

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

输入格式

从标准输入读入数据。

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

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

输出格式

输出到标准输出。

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

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

样例一

input

3
8
9
10

output

-1
3 6 6 6
-1

提示

别紧张,你这样没事。

限制与约定

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

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

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
8
9
10
-1
3 6 6 6
-1