Kaosar and Minimization#12437

Kaosar and Minimization

2 seconds

256 megabytes

Medium

you are given a integer $n$ you have to determine for any two integer $x, y$ what's the minimum value of

∣ n - x^{y} ∣ + ∣ x - y ∣

|n-x^y|+|x-y|

Here $∣ x ∣$ denotes the absolute value of $x$ i.e. the magnitude of $x$ with neglecting the sign.

Input

The first line contains single integer $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — the number of test cases.

The first line of each test case contains single integer $n$ $(1 \leq n \leq 1 0^{18})$ (1 \le n \le 10^{18}) — the integer of the problem.

For each test case , Output single integer — The answer to the problem.

Example 1

Loading

Subtask $1$ ( $20$ points) : $(1 \leq \sum n \leq 1000)$ (1 \le \sum n \le 1000)
Subtask $2$ ( $30$ points) : $(1 \leq \sum n \leq 1 0^{6})$ (1 \le \sum n \le 10^6)
Subtask $3$ ( $150$ points) : No additional constraints

∣ n - x^{y} ∣ + ∣ x - y ∣

(1 \leq t \leq 1 0^{4})

(1 \leq n \leq 1 0^{18})

(1 \leq \sum n \leq 1000)

(1 \leq \sum n \leq 1 0^{6})