P6068 "MdOI R1" GCD? GCD!

Ling likes $\mathrm{gcd}$, that is, the **greatest common divisor**. If you do not know what the greatest common divisor is, you can visit [Greatest Common Divisor - OI Wiki](https://oi-wiki.org/math/gcd/). Ling gives you a positive integer $n$ and asks you to split it into the sum of three **pairwise distinct** positive integers $a, b, c$, such that $\mathrm{gcd}(a, b, c)$ is as large as possible.

**This problem has multiple test cases.** The first line contains a positive integer $T$, which indicates the number of test cases. The next $T$ lines each contain a positive integer $n$.

For each test case, output one integer per line, which is the answer, i.e., the maximum possible value of $\mathrm{gcd}(a, b, c)$. In particular, if $n$ cannot be written as the sum of three pairwise distinct positive integers, output `-1`.

[Sample Explanation] Split $12$ into $2 + 4 + 6$. It can be proven that $\gcd(2, 4, 6) = 2$ is the maximum possible value. Split $27$ into $3 + 6 + 18$. It can be proven that $\gcd(3, 6, 18) = 3$ is the maximum possible value. $5$ cannot be written as the sum of three pairwise distinct positive integers, so output `-1`. --- [Constraints] **This problem uses bundled testdata.** | Subtask ID | $n \le$ | Score | | :--------: | :-----: | :---: | | 1 | $50$ | 17 | | 2 | $500$ | 19 | | 3 | $10^5$ | 23 | | 4 | $10^9$ | 41 | For $100\%$ of the testdata, $1 \le T \le 100$ and $1 \le n \le 10^9$. Translated by ChatGPT 5