Raj has invented a binary tree that he calls R-tree. Every R-tree has the following properties-

1. Every R-tree contains a root node that stores a positive integer greater than or equal to 2.
2. Every node of an R-tree is either a leaf node (has no children) or has exactly 2 children which are R-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.

The height of the tree is defined as the number of edges from the root to the deepest leaf.

Following is a valid R-tree with root node value of 20 and height 6.

It follows from the above rules that no children are possible for a node with a prime value. The task is to find the maximum possible height of an R-tree given its root node value. Help Raj in solving this problem.

Input Format :

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 Format:

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 R-trees with root N.

Constraints:

0 < T <= 20

2 <= N <= 10¹⁴