MOHIBTREE - Keyur and Mohib Tree

This Time Keyur (Singal) has been challenged by his friend Nishant (Vaju). As Keyur's programming skills are very poor, he asked you to help him. So as a great programmer you have to help Keyur. The challenge is as follows:

Keyur has given a binary tree Mohib-tree. Every Mohib-tree has the following properties:

  1. Every Mohib-tree contains a root node that stores a positive integer greater than or equal to 2.
  2. Every node of an Mohib-tree is either a leaf node (has no children) or has exactly 2 children which are Mohib-trees as well.
  3. The sum of values of children nodes is always equal to the value of the parent node.
  4. Value of at least one of the children nodes divides the parent value.
  5. The height of the tree is defined as the number of edges from the root to the deepest leaf.

The following are valid Mohib-Trees:

      6                   6
     / \                 / \
    2   4               3   3
       / \
      2   2

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with one line with one integer N, which represents the value of the root node.

Output

For each test case, output one line containing "Case #x: ", where x is the test case number (starting from 1). Then, for every value N in the test case, output the maximum possible height of all Mohib-trees with root N.

Constraints

0 < T <= 20

2 <= N <= 1014

Sample

Input:
3
2
6
31

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

Added by:MoHib85
Date:2016-01-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2022-06-24 09:50:17 Sushovan Sen
General suggestion for anyone getting WA for o/p format. Easiest way to deal with it is to copy-paste answer from here to your code and make necessary changes.
2021-10-06 21:35:03 Waseem Ahmed
Interesting problem
2016-04-06 11:41:20 TUSHAR SINGHAL
wtf ... changed a variable from int to long long .. and submission verdict changed from tle to AC .... don't know why .. :p
2016-02-28 17:19:59
o/p format caused me 3 WA..!! otherwise easy one..!!

Last edit: 2016-02-28 17:36:31
2016-02-16 14:15:08 Soma
@author : can u tell me why am i getting WA? submission id := 16226690

edit: AC

Last edit: 2016-02-26 11:56:54
2016-02-05 05:43:30
easy! brute force. java takes 0.5 secs
2016-02-03 15:32:53 varun bumb
EASY but nice!

Last edit: 2016-02-03 15:33:11
2016-02-03 02:11:49 ivanilos
@Lets_Code
There is a space after the colon, so the first sample case is ('b' used for blank for clarity)
Caseb#1:b0
2016-02-02 20:23:18 Lets_Code
Please make the output format clear...is there any space between "colon" and "answer"?? Bcz in output format, u havnt given any space there but in testcase output, there is a space between "colon" and "0".
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.