Description

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?

Input Format

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.

Output Format

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!.

1
4

3

1
0

NO!

Hint

「Sample 1 Explanation」

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