Efa loves numbers. She thinks a number is powerful if it can be expressed in the form xy where x and y are both positive integers greater than 1. For example, 8 and 36 are powerful as we can express 8 as 23 and 36 as 62, but 3 and 14 are not.
You are given a number n. Find the minimum positive integer p such that (n×p) is powerful.
Input
The first line contains a single integer t(1≤t≤1000)− the number of test cases.
Each test case consists of one line containing the integer n(1≤n≤1012).
Output
For each test case, print one integer p in a single line.