Tim and Julia‘s life filled with joy, when little Tim happened to them. To train little Tim, they decided to give him one small puzzle every day. One day, Julia came up with a question that amazed little Tim and he was having a hard time solving it. Help little Tim with the question as follows.

He is given a positive integer. He can perform any one of the following 3 steps.

1.) Subtract 1 from it. (n = n - 1)

2.) If it’s divisible by 2, divide by 2. (If n % 2 == 0, then n = n / 2)

3.) If it’s divisible by 3, divide by 3. (If n % 3 == 0, then n = n / 3)

Given a positive integer n and your task is to find the minimum number of steps that reduces down n to 1(one).

Input

First line of input contains t denoting number of test case. Each test case contains a number n. ( given by Julia)

Output

The output contains the number of steps it took to reduce the given number n to 1.

Constraints

1 ≤ T ≤ 100

0 < N ≤ 2 * 10000000 ( 10 to power 7)