# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Powerful Number

By adnan_toky · Limits 1s, 512 MB

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

InputOutput
5
1
16
116
7936
1935360

4
1
29
31
210


### Statistics

43% Solution Ratio

NirjhorEarliest, 1M ago

arnab_1810043Fastest, 0.0s

anisur_rahmanLightest, 131 kB

jewel.samaShortest, 987B