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