题目内容

木工坊一次要处理 $q$ 根木料。每根木料的长度是正整数 $x$。开料规程规定：只能用「奇数素数」作为最小齿距去切开木料，也就是要找 $x$ 的最小奇素因子。若长度是 $2$ 的幂，则不存在大于 $1$ 的奇数因子，这根木料无法按规程开料，记为 -1。请对每根木料给出这个齿距。

形式化地：对每个 $x$，输出它的最小奇数素因数；若不存在，输出 -1。

约束：

• 1 $\le$ $q$ $\le$ $100$
• 2 $\le$ $x$ $\le$ 100000000000000

输入描述

第一行一个整数 $q$（1 $\le$ $q$ $\le$ $100$），表示随后要处理的木料根数。

接下来 $q$ 行，每行一个整数 $x$（2 $\le$ $x$ $\le$ 100000000000000），表示一根木料的长度。

输出描述

输出 $q$ 行，每行一个整数：对应木料的最小奇素因子；若不存在，输出 -1。

样例1

输入

4
21
8
25
77

输出

3
-1
5
7

说明

• 21 $=$ 3 $\times$ 7，最小奇素因子是 3
• 8 $=$ 2^3，没有奇数素因子
• 25 $=$ 5^2，最小奇素因子是 5
• 77 $=$ 7 $\times$ 11，最小奇素因子是 7

样例2

输入

1
16

输出

-1

说明

16 $=$ 2^4，无法按规程开料。

样例3

输入

2
9
14

输出

3
7

说明

• 9 $=$ 3^2，答案为 3
• 14 $=$ 2 $\times$ 7，去掉因子 2 后剩下 7