---

Problem setter: Raihat Zaman Neloy, ACM ICPC World Finalist, 2016-17

Jahangirnagar University (JU)

---

You are given a positive integer N. You can perform any of the following operations in each

step:

1. If it is divisible by 2 then, divide it by 2.

2. If it is divisible by 3 then, divide it by 3.

3. Subtract 1 from that number.

Now you have to calculate the minimum number of steps required to reach 1.

Input Format

First line of input will consist of an integer T (T<=10^5), indicates the number of test cases

follow. Then there will be T lines, where each line contains a number N (1<=N<=10^6).

Output Format

For every test case, you need to print one line containing the minimum number of steps

required to reach 1.

Samples