Một số nguyên dương ~X~ được gọi là số đặc biệt nếu không tồn tại số nguyên ~Y > 1~ nào mà ~Y^2~ là ước của ~X~.

Cho số nguyên dương ~N~, tìm ước lớn nhất của ~N~ là số đặc biệt ?

Input

Dòng đầu tiên chứa số bộ test ~T~.

Trong ~T~ dòng sau, mỗi dòng chứa một số nguyên dương ~N~.

Giới hạn:

• ~1 \le T \le 10^5.~
• Subtask1 ~(50\%)~: ~1 \le N \le 10^5.~
• Subtask2 ~(50\%)~: ~10^5 < N \le 10^{12}~.

Output

Gồm ~T~ dòng, mỗi dòng ghi kết quả của bộ test tương ứng.

Example

Input

2
10
12

Output

10
6