Our social:

Altimetrik Java Hiring Challenge | Powers Everywhere! | Answer

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 be 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 ?


Image result for program
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:
1T25.
1Q105.
1N109.
Note: In large Input files: use faster input, output methods.


Sample Input
(Plaintext Link)

1
2
11
25

Sample Output
(Plaintext Link)

2
0
Explanation
The nearest special number from 11 is 9=32, absolute difference = 2.
25 is a special number.


                                 ANSWER