无穷的迭代器

题目背景

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

CPP

1
4

样例输出 #1

CPP

样例 #2

样例输入 #2

CPP

1
0

样例输出 #2

CPP

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

T366125

讨论操作