『MdOI R1』GCD? GCD!
题目描述
灵喜欢 $\mathrm{gcd}$，也就是 **最大公约数**。如果你不知道什么叫做最大公约数，你可以访问 [最大公约数 - OI Wiki](https://oi-wiki.org/math/gcd/)。
灵给了你一个正整数 $n$，要你把它分成三个 **互不相等的** 正整数 $a,b,c$ 之和，使得 $\mathrm{gcd}(a,b,c)$ 最大。
输入输出格式
输入格式
**本题有多组数据**。
第一行一个正整数 $T$，表示数据组数。
接下来 $T$ 行，每行一个正整数 $n$。
输出格式
对于每组数据，一行一个整数，表示答案，即最大的 $\mathrm{gcd}(a,b,c)$ 。
特别地，如果 $n$ 无法分成三个互不相等的正整数之和，请输出 `-1`。
输入输出样例
输入样例 #1
3
12
27
5
输出样例 #1
2
3
-1
说明
【样例解释】
将 $12$ 分成 $2+4+6$，可以证明 $\gcd(2,4,6)=2$ 为可能达到的最大值。
将 $27$ 分成 $3+6+18$，可以证明 $\gcd(3,6,18)=3$ 为可能达到的最大值。
$5$ 无法分成三个互不相等的正整数之和，输出 `-1`。
---
【数据范围】
**本题采用捆绑测试。**
| 子任务编号 | $n\leq$ | 分值 |
| :--------: | :-----: | :--: |
| 1 | $50$ | 17 |
| 2 | $500$ | 19 |
| 3 | $10^5$ | 23 |
| 4 | $10^9$ | 41 |
对于 $100\%$ 的数据，$1\le T \le 100$，$1\le n\le 10^9$。