Description

Orange非常喜欢平方数，但是很可惜，在自然界中，平方数总是稀少的。于是Orange决定退而求其次，他想知道一个数 $n$ 中，最大的平方因子是多少？请你帮助他解决这个问题。

平方因子：若 $a^2 | n$，我们则称 $a^2$ 是 $n$ 的平方因子。

$a | b$ 表示整除关系，即 $b$ 被 $a$ 整除，数学上表示为，存在一个非负整数 $k$ 满足 $k \times a = b$。

Format

Input

输入包含多组测试数据，第一行为一个整数 $T(T \le 10^4)$，表示测试数据数量。

对于每组测试数据，输入包含一个整数 $n(1 \le n \le 10^{12})$。

Output

对于每组测试数据，输出一行，包含一个整数表示答案。

Samples

5
75
81
8
10
12

25
81
4
1
4