无穷的迭代器
题目背景
[The English statement for T3](/problem/U508232)
You can also see the pdf at the bottom of the chinese problem statement.
题目描述
对于实数 $ r $，记一次操作为：
* 找到不小于 $ r $ 的最小整数即 $ \lceil r \rceil $，并将 $ r $ 的值乘上 $ \lceil r \rceil $。
现在给定非负整数 $ k $，对于 $ r=k+\frac{1}{2} $，至少需要对 $ r $ 进行几次操作才能使 $ r $ 为整数？
输入输出格式
输入格式
本题多测，第一行一个整数 $ T $ 代表数据组数。
对于每组数据：
一行一个整数 $k$，含义见题目描述。
输出格式
对于每组数据：
若可以变成整数，输出一行一个整数代表你找到的最小的次数。
若不能变成整数，输出一行 `NO!`。
输入输出样例
输入样例 #1
1
4输出样例 #1
3输入样例 #2
1
0输出样例 #2
NO!说明
**【样例 1 解释】**
| 操作次数 | $ r= $ |
|:-:|:-:|
| 初始 | $ \frac{9}{2} $ |
| $ 1 $ | $ \frac{45}{2} $ |
| $ 2 $ | $ \frac{1035}{2} $ |
| $ 3 $ | $ 268065 $ |
**【数据规模与约定】**
**提示：本题采用捆绑计分。**
对于 $ 100\% $ 的数据，$ 1 \le T \le 20 $，$ 0 \le k \le 10^{18} $。
* Subtask 1（15 pts）：$ 1 \le k \le 10 $。
* Subtask 2（40 pts）：$ 1 \le k \le 100 $。
* Subtask 3（45 pts）：$ 0 \le k \le 10^{18} $。