P11310 Iterators for Infinity

You can also see the pdf at the bottom of the chinese problem statement.

For a real number $ r $, defining an operation as: * $ r \leftarrow r\lceil r \rceil $（$ \lceil r \rceil $ is smallest integer that is not less than r）. Give a nonnegative integer $ k $，what is the minimum number of operations that need to be performed on $ r=k+0.5 $ to make $ r $ an integer?

This is a multiple test problem, where the first line an integer $ T $ represents the number of data sets. For each group of data: One integer $ k $ in the first line, the meaning of which is described in the description section.

If it can be made into an integer, output one line with an integer representing the smallest number of times you found it. If it cannot be made into an integer, output a line `NO!`.

**「Sample 1 Explanation」** | Times | $ r $ | |:-:|:-:| | $ 0 $ | $ \frac{9}{2} $ | | $ 1 $ | $ \frac{45}{2} $ | | $ 2 $ | $ \frac{1035}{2} $ | | $ 3 $ | $ 268065 $ | **「Data sizes and conventions」** **This question is scored as a bundle.** For 100% of data, $ 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} $。