无穷的迭代器

对于实数 $ r $，记一次操作为：

• 找到不小于 $ r $ 的最小整数即 $ \lceil r \rceil $，并将 $ r $ 的值乘上 $ \lceil r \rceil $。

现在给定非负整数 $ k $，对于 $ r=k+\frac{1}{2} $，至少需要对 $ r $ 进行几次操作才能使 $ r $ 为整数？

本题多测，第一行一个整数 $ T $ 代表数据组数。

对于每组数据：

一行一个整数 $k$，含义见题目描述。

对于每组数据：

若可以变成整数，输出一行一个整数代表你找到的最小的次数。

若不能变成整数，输出一行 NO!。

【样例 1 解释】

【数据规模与约定】

提示：本题采用捆绑计分。

对于 $ 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} $。