题目描述

数论大神 ydzr 正在研究数论。他得到了一个如下的函数：

作为一位神牛，他自然很快地想出了如何计算这个函数。于是他开始思考对于一个给定的 $x$，如何找到一个最小的正整数 $n$ 使得 $f(n)=x$。这也当然难不倒他。于是他把这个问题交给了你，想检验你的数论水平。由于只回答一个问题无法展现你的水平，他将会问你 $T$ 次。

输入格式

第一行一个数，表示 $T$。

后面 $T$ 行，每行一个正整数，表示 $x$。

输出格式

输出 $T$ 行，每行一个整数，如果存在解则输出最小的 $n$，否则输出 $-1$。

样例

4
20
21
1
7

10
7
1
-1

数据范围