Cho số nguyên dương $n$. Hãy cho biết số chính phương lớn nhất là ước của $n$.

Input

• Dòng đầu tiên chứa số nguyên $T(1 ≤ T ≤ 10^5 )$, là số lượng test.

• $T$ dòng tiếp theo mỗi dòng chứa số nguyên $n(1 ≤ n ≤ 10^7)$.

Output

• Gồm $T$, mỗi dòng ghi một số nguyên là kết quả của test tương ứng.

Ràng buộc

• Subtask 1: $1 ≤ n, T ≤ 1000$.

• Subtask 2: $T ≤ 10^5, n ≤ 10^7$.

Sample Input

6
4 
18 
8 
24 
10
20

Sample Output

4
9
4
4
1
4