MST1 - Minimum Step To One

no tags 

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 it is divisible by 2, divide by 2. (if n % 2 == 0, then n = n / 2)
  3. If it is divisible by 3, divide by 3. (if n % 3 == 0, then n = n / 3)

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

Input

The input contains an integer T (1 ≤ T ≤ 100) number of test cases. Second line input is N (0 < N ≤ 2*107) that indicates the positive number.

Output

For each case, print the case number and the minimum number of steps.

Example

Input:
3
1
4
7

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

Explanation

  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)

hide comments
rohan843: 2022-07-03 21:26:02

for me, using a dp array to store results across test cases, and top down recursion worked.

kururugisuzaku: 2022-06-29 20:47:12

problem is good but the judge uses a 32-bit architecture making my correct recursive solution to cause a runtime error use a modern judge don't waste time here

solvertobe: 2020-10-07 15:21:29

Ac in on go. My third DP.

deerawat: 2020-05-24 22:04:03

AC IN ONE GO

raghav6: 2018-12-31 14:31:57

Use Vector instead of the Array it is more time and space efficient.

ram_24: 2018-06-25 06:10:08

output format cost me 1 WA :(

adityavr9: 2018-06-23 06:48:02

Please note the Output Format. It is:
Case <Case Number>: <Answer>

Shikhor Roy: 2018-05-28 18:55:51

Recursive DP in java causes NZEC ERROR (may be stack overflow occur)...but iterative DP is fine !!!

Last edit: 2018-05-28 18:56:35
asif_mohammad: 2018-02-14 10:57:40

ACC in one go. BFS

bholebaba: 2018-01-29 21:59:58

All these time I was printing just the required values and not the case nos :(,


Added by:Shipu Ahamed
Date:2013-05-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64