408505: GYM103158 J 2wix+

Yasser is a coach in the ACPC. One day he decided to teach his trainee Khaled Hamed some basic Math. Since Khaled is ... well Khaled, Yasser needed some fun activity to teach him.

Yasser brought some 2wix chocolates with him since they have $$$2$$$ bars and gave Khaled a number $$$N$$$.

"You are going to create expressions with only one operation $$$(+)$$$ using Parenthesis "$$$()$$$" and the number $$$2$$$ to represent the number $$$N$$$".

For example: $$$8$$$ can be represented by at least 4 $$$2s$$$

$$$8 = \displaystyle ((2+2)+2+2) $$$

Khaled wanted to know if it's possible to create such an expression, and if so what the minimum number of $$$2s$$$ needed to create an expression that evaluates to $$$N$$$, so he can get the remaining chocolates.

The following part was written by Pillow:

Khaled is a blue coder so he asked you (The genius solving ACPC 2021 Kickoff Problems) to find the minimum number of $$$2s$$$ needed to represent $$$N$$$.

Note that you are allowed to use only the number $$$2$$$, you cannot use $$$22$$$, $$$222$$$, ...

The first line consists of a single integer $$$T$$$ $$$(1 \leq T \leq 10^5)$$$, denoting the number of test cases.

Each test case contains a single integer $$$N$$$ $$$(0 \leq N \leq 2 \times 10^5)$$$.

For each test case, print a single line containing a single integer denoting the minimum number of 2s required to represent N.

If there is no answer, print $$$-1$$$.

3
2
4
9

1
2
-1

The answer of $$$2$$$ is $$$1$$$, since we have only one $$$2$$$.

The answer of $$$4$$$ is $$$2$$$, we can use $$$(2+2)$$$.

The answer of $$$9$$$ is $$$-1$$$, since you cannot create an expression with only $$$2s$$$ and $$$+$$$ operations.