Problem Statement

The execution time limit for this problem is 4000ms.

Problem Statement

An integer that can be expressed as $a^n$ with an integer $a \geq 2$ and a positive integer $n$ is called an $n$-th power.
You are given $Q$ integers $N_1, \dots, N_Q$, each at least $2$, from the input.
For each $q = 1, \dots, Q$, find the positive integer $n_q$ such that $N_q$ is an $n_q$-th power and, whenever $n > n_q$, $N_q$ is not an $n$-th power.

Input

$Q \\ N_1 \\ \vdots \\ N_Q$

$1 \leq Q \leq 10^5,$
$2 \leq N_q \leq 10^{12}$
are integers.

Output

Find $n_q$ and output

$n_1 \\ \vdots \\ n_Q$

Sample

2
16
19

4
1