题目描述

在沈阳化工大学的ACM集训队里，大家正在讨论如何在一次算法比赛中脱颖而出。为了让大家更好地理解约数枚举和贪心分配技巧，学长「寂空」提出了一个有趣的数学问题：给定一个正整数 $n$，能否将它拆分成三个正约数之和，同时让这三个数的乘积最大？大家一听，都觉得既要考虑约数，又要优化乘积，思路非常具有挑战性，纷纷跃跃欲试。

给定一个正整数 $n$，请找到三个正整数 $x$,$y$,$z$，满足：

1. $n = x + y + z$
2. $x \mid n、y \mid n、z \mid n$（即三者都是 $n$的约数）；
3. 使得乘积 $x \times y \times z$ 尽可能大。

如果存在多组解，输出其中乘积最大的那个；如果不存在任何符合条件的三元组，则输出$-1$。

输入格式

第一行包含一个正整数 $T(1 \le T \le 10^6)$，表示测试用例的数量。
接下来有$T$行，每行包含一个正整数 $n(1 \le n \le 10^6)$。

输出格式

对于每个测试用例，输出一个整数——所求的最大乘积；如果无解，则输出$-1$。

样例

3
1
2
3

-1
-1
1

提示

$1$和$2$无法表示成三个数的和，$3 = 1 + 1 + 1$满足题意。