Today Omar is studying a math lecture, then he decides to solve its exercises. After finishing the study, Omar now thinks in the following question. There are many special numbers that could be in the formula \(b ^ e\) where b indicates the base number, e indicates the power number. But there are also many numbers that couldn't be formed in this formula so the question is to find the minimum absolute difference between a given number N and the nearest special number.

Note: for a special number, \(b,e\) integers \(> 1\).

Can you help Omar in this exercise ?

Input:

Given an integer T, number of test cases.
For each test case:
In the first line: given an integer Q, the number of queries.
Then next Q lines follow, each line has an integer N.

Output:

For each test case: answer the Q queries, every result in a separate line.

Constraints:

\(1 \le T \le 25\).
\(1 \le Q \le 10 ^ 5\).
\(1 \le N \le 10 ^ 9\).

Note: In large Input files: use faster input, output methods.