MST1 - Minimum Step To One

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)

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

hide comments
2015-09-26 23:13:07 Arpan Mukherjee
Using dp,still getting Runtime Error Any help?

EDIT: Declare the array globally,cost me 1 WA

Last edit: 2015-09-26 23:39:51
2015-08-29 16:33:48
My First DP!!:)
2015-07-15 18:35:00 sameer Hussain
Easy DP :)

Last edit: 2015-07-15 19:02:00
2015-03-04 07:56:11 surbhit21
first DP !! :)
2014-12-22 11:10:49 nrl 7
Only 2 correct submissions in Java, due to a very odd-style of input specified. :\
2014-10-22 13:33:04 Rohit Meena
why i got wrong ans <snip>

Last edit: 2023-03-16 12:14:11
2014-10-16 12:20:33 ^_^
My first dp :)
2014-10-03 10:00:12 karan
first dp :)
2014-09-07 03:10:39 Girish Rathi
easy one
2014-08-05 19:51:08 vikrant
use dp rather than recursive
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.