408499: GYM103158 D 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 the following operations $$$(+, -, *, /)$$$ using Parenthesis "$$$()$$$" and the number $$$2$$$ to represent the number $$$N$$$.

Please note that the operation $$$/$$$ corresponds to integer division in which the fractional part (remainder) is discarded.

For example: $$$9$$$ can be represented by at least five $$$2s$$$

$$$9 = \displaystyle ((2+2)*2)+\frac{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
5

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

The answer of $$$4$$$ is $$$2$$$, we can use either $$$(2+2)$$$ or $$$(2*2)$$$ both have only two 2s.

The answer of $$$9$$$ is $$$5$$$, one of the minimum possible expressions is $$$(((2+2)*2)+(2/2))$$$.