Efa loves numbers. She thinks a number is powerful if it can be expressed in the form $x^y$ where $x$ and $y$ are both positive integers greater than $1$. For example, $8$ and $36$ are powerful as we can express $8$ as $2^3$ and $36$ as $6^2$, but $3$ and $14$ are not.

You are given a number $n$. Find the minimum positive integer $p$ such that $(n\times p)$ is powerful.

Input

The first line contains a single integer $t$ $(1 \leq t \leq 1000)$ $-$ the number of test cases.

Each test case consists of one line containing the integer $n$ $(1 \leq n \leq 10^{12})$.

Output

For each test case, print one integer $p$ in a single line.

Sample

Input	Output
5 1 16 116 7936 1935360	4 1 29 31 210