Draw and Score

The great programmer Froogrammer challenged you with the following game on a binary tree: Every node in a binary tree has at most two children — the left child and the right child. The subtree rooted at the left child is called the left subtree and the subtree rooted at the right child is called the right subtree. In the example image, the left child of node 2 is node 4 and node 3 has no left child. A node is called balanced if: (1) It has a left child and a right child and (2) The size of the left subtree is equal to the size of the right subtree. (Size of a tree being the number of nodes in it) In the example image, node 1 and 2 are balanced. The other nodes are called unbalanced. You are playing a game where you have to draw a binary tree with N nodes. Initially you draw the root node. Then at each of the N − 1 following steps:

1. From the nodes that you have already drawn, chose a node that has less than or equal 1 child.
2. Draw a new node as the left child or the right child of the chosen node. Note that, if the chosen node has no child, you are free to decide on which side you are going to draw the new node. There is a scoring system of this game. Each node has a score which is initially zero. Whenever you draw a new node: (a) 0 or more nodes become balanced those were unbalanced before, (b) 0 or more nodes become unbalanced those were balanced before, (c) Other nodes remain same as before. The score of all the nodes that become balanced as a result of drawing the new node are incre- mented by 1. The score of other nodes stay unchanged. Your target is to maximize the sum of scores of all the nodes at the end of the game. For this problem you will be given the value of N. You have to calculate the maximum possible sum of scores. Input The first line of the input will contain an integer T that denotes the number of test cases that follow. (T ≤ 5000). Each of the next T lines contains the value of N denoting the number of nodes of the binary tree. (1 ≤ N ≤ 1015). It is guaranteed that, the answer will fit in 64 bit signed integer. Output Foreachcase,printalineoftheform‘Case : ’,wherexisthecasenumberandyisthe maximum possible score.

2/2 Sample Input 2 2 7 Sample Output Case 1: 0 Case 2: 5