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