Background

Special for beginners, ^_^

Description

徐老师把一个大于 1 的整数 $x$ 写在黑板上，对全班布置了一份作业：

质数是大于 1 且除了 1 和自身没有其他因数的数；

合数是大于 1 且不是质数的数；

特别地，1 既不是质数也不是合数。

现在：在 $1 \le y < x$ 的范围里找一个 $y$，让 $x \oplus y$ 变成合数，写出最小的与x奇偶性相同的y，要是没有，就写 $-1$。

Format

Input

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$（$1\le T\le 10^3$），代表数据组数。每组测试数据描述如下：

• 在一行上输入一个整数 $x$（$1\le x\le 10^{18}$），表示徐老师写下的数。

Output

输出符合题意的$y$，没有则输出-1

Samples

3
1
1
4

-1
-1
2

Limitation

1s, 1024KiB for each test case.