#### 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