Find The Path

Author: Abu Rayhan Ahmad


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

Input
2 5 12
Output
3 3
Limits
Language Time Memory
GNU C 11 2s 1024MB
GNU C++ 14 2s 1024MB
GNU C++ 11 1s 512MB
Statistics
Login To Submit