問題文

正整数 $a,b(a\ge 1,b\ge 2)$ を用いて $a^b$ と表わされる正整数を 累乗数 といいます．

$K$ 番目に小さい累乗数を求めてください．

$T$ 個のテストケースが与えられます．

入力

$T$
$cas{e}_1$
$⋮$
$cas{e}_T$

$K$

• $1\le T\le 500$
• $1\le K\le {10}^9$
• 入力は全て整数である．

出力

$T$ 行出力してください．$i$ 行目には $i$ 番目のテストケースの $K$ について，$K$ 番目に小さい累乗数を出力してください．

サンプル

10
1
2
3
4
5
6
7
8
9
10

1
4
8
9
16
25
27
32
36
49