Powers Everywhere!
Tag(s):

## Binary Search, Data Structures, Easy, Implementation, Math

Problem
Editorial
Analytics

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.

SAMPLE INPUT
1
2
11
25
SAMPLE OUTPUT
2
0
Explanation

The nearest special number from $11$ is $9 = 3 ^ 2$, absolute difference = $2$.
$25$ is a special number.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...