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 <= 10¹⁴

Sample

Input:
3
2
6
31

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