题目描述

灵喜欢 $\mathrm{gcd}$，也就是 最大公约数。如果你不知道什么叫做最大公约数，你可以访问 最大公约数 - OI Wiki。

灵给了你一个正整数 $n$，要你把它分成三个 互不相等的 正整数 $a,b,c$ 之和，使得 $\mathrm{gcd}(a,b,c)$ 最大。

输入格式

本题有多组数据。

第一行一个正整数 $T$，表示数据组数。

接下来 $T$ 行，每行一个正整数 $n$。

输出格式

对于每组数据，一行一个整数，表示答案，即最大的 $\mathrm{gcd}(a,b,c)$ 。

特别地，如果 $n$ 无法分成三个互不相等的正整数之和，请输出 -1。

3
12
27
5

2
3
-1

提示

【样例解释】

将 $12$ 分成 $2+4+6$，可以证明 $\gcd(2,4,6)=2$ 为可能达到的最大值。

将 $27$ 分成 $3+6+18$，可以证明 $\gcd(3,6,18)=3$ 为可能达到的最大值。

$5$ 无法分成三个互不相等的正整数之和，输出 -1。

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据，$1\le T \le 100$，$1\le n\le 10^9$。