P5623 [Celeste-A] Sever the Skyline

> 废弃的城市里充满了机关和陷阱，而今晚，我们将 > ——划破这城市的天际线

Madeline 来到了被废弃的城市，这座城市里满是机关，还有一台不知所谓的机器在向外发射着光信号。 通过 Madeline 强大的观察力，她发现光信号其实对应着某种冲刺顺序，按照顺序冲刺之后，她发现她冲刺的轨迹构成了这座废弃城市的天际线。 多年以后，当 Madeline 回忆她登山的旅途时，已经不记得这座城市的天际线长什么样了，只记得所有建筑高度的和为 $n$，并且每座建筑的高度可以表示为 $p^iq^j$，$p,q$ 为素数且 $i,j \geq 0,i+j\geq 1$。 Madeline 知道，这座城市的天际线是很有美感的，不存在两座建筑使得它们的高度成**整倍数**关系(1倍也是整倍数)，例如若存在一座高度为 $2$ 的建筑，就一定不能存在高度为 $4$ 的建筑。 由于 Madeline 的记忆相当模糊，所以她可能要求你多次对于一个特定的记忆给出一个合法的天际线。

无

无

对于前 $30\%$ 的数据，保证 $n \leq 100$， 对于另外 $20\%$ 的数据，保证 $p,q \leq 3$ 对于 $100\%$ 的数据，保证 $1 < n \leq 10^{18}, p,q \leq 40, p < q, T \leq 10000$ 对于最后 $30\%$ 的数据，采用捆绑测试，仅当您通过了所有测试点才能得分。 保证数据的生成方式为： 均匀随机两个质数 $p,q$，随机选择若干个 $p^iq^j$，保证它们不成倍数，将 $p^iq^j$ 的和作为 $n$，若这组数据满足当前数据点的要求，则保留，若不满足，则重新生成。 对于最后 $30\%$ 数据点，对于 $n$ 要求 $n > 10^{17}$。 对于最后 $30\%$ 数据点中的部分测试点，要求至少选出 $4$ 个 $p^iq^j$ 来组成 $n$。 **本题 spj 认可的格式为：行末无空格，每组输出行末换行。** **若格式不正确，您可能会获得 UKE**