Omkar was getting bored in this lockdown period so he thought to explore his store room (believe me it's a nice place to “explore”!) where he found an old calculator. The calculator he got is weird AF as it has only three buttons labeled as: 

*2, *3, ++

The calculator is weird not only because of this but also because there was no number button at all! (Dude, it has “on” and “off” buttons. Likh diya warna kuch log yahaan bhi bakwaas karne aa jaate!) 

Initially (after pressing the “on” button) the screen has 0. Now Omkar decides to do some “programming experiments” with this calculator (yeah, you got it right… that’s what legends do when they get such a thing! #respect). Omkar “believes in himself”! He can bet that lockdown is gonna extend, how a student like him can sit without studying for this long!

Omkar wants to figure out an algorithm to find the minimum number of operations needed to get a number “n” on the screen! (Print -1 if you believe on yourself like him and can guarantee that he can't get that number ever on the screen!)

Hey, wait! If you think I wanna ask you to help him then, then lemme first clear you that you are wrong! You have to write a correct code which he can't understand easily (doosron ka kaam badhaane mein mazaa aata hai na tumhe ¬_¬).  Also make sure your solutions don't bore him :/ 

Here is a message from him for you (copied then modified from StackOverflow):

For the brave souls who get this far: You are the chosen ones, the valiant knights of programming who toil away, without rest, solving our most awful questions. To you, true saviors, kings of men, I say this: never gonna give you up, never gonna let you down, never gonna run around and desert you. Never gonna make you cry, never gonna say goodbye. Never gonna tell a lie and hurt you.

Input Format:

First line contains an integer t representing the number of test cases. Each of the next t lines contains an integer N_i.

Output Format:

Corresponding to each test case the minimum number of operations required. (-1 if you think he can’t get that number on the calculator screen).

Constraints:

1 ≤ t ≤ 100

0 ≤ N_i < USHRT_MAX

Sample Input: 

2
1
5

Sample Output:

1
4

Explanation:

For N_i = 1, we need to just press the ++ button once.

For N_i = 5, we need to press ++ (screen = 0 + 1 = 1), ++ (screen = 1 + 1 = 2), *2 (screen = 2 * 2 = 4), ++ (screen =  4 + 1 = 5) (4 operations). One could also press ++ (screen = 0 + 1 = 1), *2 (screen = 1 * 2 = 2), *2 (screen = 2 * 2 = 4), ++ (screen = 4 + 1 =5) or ++ (screen = 0+ 1 = 1), *3 (screen = 1 * 3 = 3), ++ (screen = 3 + 1 =4 ), ++ (screen = 4 + 1 = 5). In each of these sequences we have to make at least 4 operations. We can't get 5 in less than 4 steps.

Line of Motivation: The output value never exceeds 20.