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