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 xyx^y where xx and yy are both positive integers greater than 11. For example, 88 and 3636 are powerful as we can express 88 as 232^3 and 3636 as 626^2, but 33 and 1414 are not.

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

Input

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

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

Output

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

Sample

InputOutput
5
1
16
116
7936
1935360
4
1
29
31
210

Discussion

Statistics


43% Solution Ratio

NirjhorEarliest, 1M ago

arnab_1810043Fastest, 0.0s

anisur_rahmanLightest, 131 kB

jewel.samaShortest, 987B

Submit

Login to submit

Editorial

The number xyx^yxy is powerful. Let the prime factorization of xxx be p1e1×p2e2×p3e3×…×pkekp_1^{e_1}...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.