题目背景

The English statement for T3

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
4

3

1
0

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