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
cbdavide: 2017-07-28 23:16:31

First DP solution, I feel really, really happy :)
After two TLE submissions using a map as a table, until I changed it to an array.

Last edit: 2017-07-28 23:17:44
ayush_1996: 2017-07-15 09:49:52

My First DP :D

Omar: 2017-06-14 07:02:14

I solved it recursive + memo (top-down) in 0.48 sec. , and this is my code <snip>

Last edit: 2023-03-16 12:13:20
ekjot_kaur281: 2017-06-12 20:22:49

Got 3 WA because i didnt give space after colon

Nafis Islam: 2017-05-17 16:21:06

Top down dp works :D

cyanide_mind: 2017-04-08 20:03:21

My First DP :)

samarjeet27: 2016-04-15 12:04:16

Why does Global DP Array gives AC while Local Array gives WA ?

darkhire21: 2016-04-10 08:22:57

TOP down TLE ...!!

gohanssj9: 2016-02-24 15:33:12

first dp :D


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