Submit Best Submissions All Submissions

173. Minimum Step To One


Problem Statement:
Problem statement is very easy. On a positive integer, you can perform any one of the following 3 steps:

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

  2.) If its divisible by 2, divide by 2. (if n % 2 == 0, then n = n / 2)

  3.) If its divisible by 3, divide by 3. (if n % 3 == 0, then n = n / 3)

Given a positive integer n and your task is find the minimum number of steps that takes n to one.


Input Format:
An integer T (1 <= T <=100) denoting the number of test cases followed by T lines. Each containing a single integer N (1 <= N <= 2*107).


Output Format:
For each case, print the case number and minimum steps like the following examples.


Sample Input:
3 1 4 7


Sample Output:
Case 1: 0 Case 2: 2 Case 3: 3


Notes:
  1.) For N= 1, output: 0

  2.) For N = 4, output: 2 (4 /2 = 2 /2 = 1)

  3.) For N = 7, output: 3 (7 -1 = 6 /3 = 2 /2 = 1)





Added by: shipu
Added at: 2014-07-24 15:46:07 UTC
Time Limit: 1 second
Partial score: No
Source:Shipu Ahamed, Dept. of CSE, Bangladesh University of Business and Technology (BUBT)