公约数

题目描述

给定正整数 $m$，请你将它分解为三个互不相同的正整数 $x, y, z$，在满足 $m = x + y + z$ 的前提下，使得 $x, y, z$ 的最大公约数最大——换言之，要找到最大的正整数 $d$，使得 $d$ 是 $x, y, z$ 共同的约数。

输入格式

第一行一个正整数 $N$，表示测试点包含 $N$ 组数据。

接下来 $N$ 行，每行一个正整数 $m$，表示要分解的数字。

输出格式

共 $N$ 行，依次表示对应 $m$ 的最大计算结果。

特别地，当 $m$ 无法分解为满足要求的 $x, y, z$ 时，应输出 $-1$。

样例 #1

样例输入 #1

3
27
12
5

样例输出 #1

3
2
-1

提示

当 $m = 27$ 时，可令 $x = 3, y = 6, z = 18$，此时 $x, y, z$ 的最大公约数为 $3$。可以证明，无法找到比 $3$ 更大的最大公约数。

【数据规模与约定】

本题包含四个子任务，每个子任务捆绑计分：

子任务	$m \leq$	分值
1	$50$	17
2	$500$	19
3	$10^5$	23
4	$10^9$	41

对于全部数据，保证 $1 \le N \le 100$，$1 \le m \le 10^9$。