Cho số nguyên dương \(n\). Hãy viết chương trình tìm ước số lớn nhất của \(n\) mà khác \(1\) và chính nó.

Input

• Dòng thứ nhất chứa số \(T(1 \le T \le 70)\) - Thể hiện số lượng test case.
• \(T\) dòng tiếp theo, mỗi dòng chứa số nguyên n. \((1 \le n \le 10^{14})\).

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm (nếu không có đáp án thì in ra \(-1\)).

Example

5
1
2
4
6
8

-1
-1
2
3
4