Problem Description

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.

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.

Input Format

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$.

Output Format

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.

3
12
27
5

2
3
-1

Hint

[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.

For $100\%$ of the testdata, $1 \le T \le 100$ and $1 \le n \le 10^9$.

Translated by ChatGPT 5