$n=a**b$You are given T number of numbers you have to turn them into zero there are two spells that you can cast the spells are: Aabra $-$ It reduces the number by two Dabra $-$ If the number can be written as n$=$a$*$b where a$!=1$ and bl$=1$ then reduce the number to max$($a$,$b$)$ Both spells take $1$ unit of energy each. Calculate minimum energy required to change number to zero.Input FormatThe first line contains the T integer. The next T lines each contain an integer. N$.$Constraints$1$n$=$a$**$b where $a1$

and $b1$ then reduce the number to max$(a,b)$ Both spells take $1$ unit of energy each. Calculate minimum

energy required to change number to zero.

Input Format

The first line contains the $T$ integer. The next $T$ lines each contain an integer, $N.$

Constraints

$1$

$in11$ hours

Submissions: $32$

Max Score: $50$

Difficulty: Medium

Rate This Challenge:

$$

More

Output Format

$T$ Output lines. Each line containing the minimum energy required $to$ convert the value $to$ zero.

Sample Input $0$

Sample Output $0$

Explanation $0$

$1$ can $be$ turned $0in$ just one spell Aabra $2$ can $be$ turbed $0in$ just one spell Aabra $3$ will require two Aabra

spells $4$ will also needs $2$ spells Aabra and Dabra $or2$ Aabras $5$ will turn into $3$ then into $1$ then $06$ will turn into

$3$ Daabra first then $1$ then $07$ will turn into $5$ then $3$ then $1$ then $08$ will turn into $4$ Aabra then $2$ more spells $9$

will turn into $3$ Aabra then $2$ more spells $10$ will turn into $5$ Aabra then $3$ more spells