Kí hiệu \(d(n)\) là tổng các ước nguyên dương của số nguyên dương \(n\), tức là: \(d(n)=\sum\limits_{k|n}k\)

Cho trước số nguyên \(c\), hãy tìm số nguyên dương \(n\) nhỏ nhất thoả mãn: \(d(n)=c\)

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 10^4)\) - Thể hiện số lượng testcase

• \(t\) dòng tiếp theo, mỗi dòng chứa số \(c(1\le c\le 10^7)\)

Output

• Ứng với mỗi testcase, in ra số nguyên dương \(n\) thoả mãn yêu cầu bài toán. Nếu không có in ra -1

Example

9
11
87
58
92
83
74
7
13
77

-1
-1
-1
-1
-1
73    
4
9    
-1

6
6
75
89
2
84
70

5
-1
-1
-1
44
-1