Cho số nguyên dương $n$, tìm thừa số nguyên tố lớn nhất của $n$ trong dãy phân tích nguyên tố của $n$.

Ví dụ:

• $n = 4 = 2^2$ => thừa số nguyên tố lớn nhất là 2
• $n$ = 14 = 2 x 7 => thừa số nguyên tố lớn nhất là 7

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên $T$ là số bộ dữ liệu vào kiểm tra, mỗi bộ dữ liệu vào gồm một dòng chứa một số nguyên dương $N$.

Ràng buộc:

• $0 < T \leq 100; 0 < n \leq 10^{10}.$

Kết quả

• in ra $T$ dòng, mỗi dòng in ra thừa số nguyên tố lớn nhất của $n$.

Ví dụ:

INPUT

3
6
15
9999999967

OUTPUT

3
5
9999999967