对于正整数 $k$ 和正整数 $f_1$，序列 $f$ 根据以下公式对 $n \ge 2$ 递归生成：

$$f_n = kn + \left\lfloor \frac{f_{n-1}}{n} \right\rfloor \cdot n$$

例如，若 $k = 4$ 且 $f_1 = 23$：

$f_1 = 23$ $f_2 = 4 \cdot 2 + 24 = 32$ $f_3 = 4 \cdot 3 + 33 = 45$ $f_4 = 4 \cdot 4 + 48 = 64$ $f_5 = 4 \cdot 5 + 65 = 85$ $f_6 = 4 \cdot 6 + 90 = 114$ $f_7 = 4 \cdot 7 + 119 = 147$

对于这样的序列，如果存在一个多项式 $P(n)$，使得对于所有 $n \ge m$ 都有 $P(n) = f_n$，但 $P(m-1) \neq f_{m-1}$，则称索引 $m \ge 2$ 为插值的起始索引。在上面的例子中，$5$ 是插值的起始索引：对于所有大于 $4$ 的索引，$f_n = P(n) = 2n^2 + 7n$，但 $f_4 = 64 \neq P(4) = 60$。

给定一个整数 $x$，请找到满足以下条件的任意参数对 $f_1$ 和 $k$ 以及索引 $m$，或者报告不存在这样的解：

• $1 \le f_1 \le 10^{10}$，$1 \le k \le 10^5$，$2 \le m \le 10^{18}$；
• $m$ 是由这些参数生成的序列的插值起始索引；
• $f_m = x$。

不等式条件非常重要。特别地，如果对于某些输入，唯一满足后两个条件的元组 $(f_1, k, m)$ 不满足第一个条件，则应报告无解。

输入格式

每个测试包含一个或多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 100$)。 每个测试用例仅包含一行，为一个整数 $x$ ($2 \le x \le 10^{18}$)。其中 $x > 10^9$ 的测试用例最多只有一个。

输出格式

对于每个测试用例，如果不存在答案，输出 -1。 否则，输出一行，包含三个整数：$f_1, k, m$ ($1 \le f_1 \le 10^{10}, 1 \le k \le 10^5, 2 \le m \le 10^{18}$)。如果存在多个解，输出其中任意一个即可。

样例

样例输入 1

4
85
7
6
637275712755506

样例输出 1

23 4 5
-1
1 2 2
-1

说明 1

对于第三个测试用例，"2 2 2" 不是正确答案，因为在这种情况下 $P(1) = f_1$，因此 $2$ 不是插值的起始索引。