题目背景

废弃的城市里充满了机关和陷阱，而今晚，我们将

——划破这城市的天际线

题目描述

Madeline 来到了被废弃的城市，这座城市里满是机关，还有一台不知所谓的机器在向外发射着光信号。

通过 Madeline 强大的观察力，她发现光信号其实对应着某种冲刺顺序，按照顺序冲刺之后，她发现她冲刺的轨迹构成了这座废弃城市的天际线。

多年以后，当 Madeline 回忆她登山的旅途时，已经不记得这座城市的天际线长什么样了，只记得所有建筑高度的和为 $n$，并且每座建筑的高度可以表示为 $p^iq^j$，$p,q$ 为素数且 $i,j \geq 0,i+j\geq 1$。

Madeline 知道，这座城市的天际线是很有美感的，不存在两座建筑使得它们的高度成整倍数关系(1倍也是整倍数)，例如若存在一座高度为 $2$ 的建筑，就一定不能存在高度为 $4$ 的建筑。

由于 Madeline 的记忆相当模糊，所以她可能要求你多次对于一个特定的记忆给出一个合法的天际线。

输入格式

第一行为一个整数 $T$，表示 Madeline 的询问次数。

接下来 $T$ 行，一行三个整数 $n,p,q$，分别表示本次回忆中建筑高度的和与题目描述中所述的 $p,q$。

输出格式

对于每组回忆输出一行若干个整数，以空格分隔，表示一组合法的天际线。

每组数据保证有解，若有多组合法的解，请输出任意一组。

请不要在行末增加多余空格，否则会 WA。(即，行末无空格)

3
15 2 3
10 2 5
416873881340965120 2 7

6 9
10
8507630225817856 19446011944726528 22224013651116032 12699436372066304 8293509467471872 4739148267126784 1354042362036224 3094953970368512 1768545125924864 32339110874054656 5279854836580352 1508529953308672 3448068464705536 3940649673949184 288230376151711744

提示

对于前 $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