After realizing that he was being too cruel to the numbers and that Christine would be happier with the mathematician, Dr. Strange offered his help to reconstruct the beauty of the numbers. So, he came up with the following problem for you to solve, again.

Given an integer \(n\), find the minimum integer \(m\) such that \(n \times m\) is a square number.

The first line contains a single integer \(t\) — the number of test cases.
The first line of each test case contains a single integer \(n\).

\(1 \leq t \leq 10^3\) 
\(1 \leq n \leq 10^6\) 
\(1 \leq m \leq 10^{10}\)

For each test case, print a single integer \(m\) — described in the statement.

Input copy	Output copy
2 10 12	10 3

Input copy	Output copy
3 1 69 75	1 69 3