Tổng các ước

Với số nguyên dương $n$, ký hiệu $d(n)$ là tổng tất cả các ước dương của $n$:

$$d(n)=\sum _{k\mid n}k.$$

Ví dụ: $d(1)=1$, $d(4)=1+2+4=7$, $d(6)=1+2+3+6=12$.

Cho số nguyên $c$, hãy tìm số nguyên dương $n$ nhỏ nhất sao cho $d(n)=c$. Nếu không tồn tại số $n$ như vậy, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $t$: số lượng truy vấn.
• Mỗi dòng trong $t$ dòng tiếp theo chứa một số nguyên $c$.

Dữ liệu ra

Với mỗi truy vấn, in ra trên một dòng:

• $-1$ nếu không tồn tại $n$ nào thỏa $d(n)=c$;
• ngược lại, in ra số $n$ nhỏ nhất thỏa mãn.

Ràng buộc

• $1\le t\le {10}^4$
• $1\le c\le {10}^7$

Ví dụ