C

Dumb Grocer Input: Standard Input Output: Standard Output

The grocer sells goods of integer amount units from 1 to n. He has a weighing scale with two pans. By this weighing device he weighs by placing goods in one pan and placing standard measuring stones in another pan. His standard measuring stone set has the following property

- Each of them has integer weight.

- The sum of all the weights of these measuring stones is exactly n.

- Each of the weights from 1 to n can be measured uniquely by selecting a subset of this measuring set. If there is multiple way to measure a weight between 1 to n then it may be problematic for the grocer.

For n = 5 the example of valid sets are {1,2,2},{1,1,1,1,1}, {1,1,3}. The examples of some invalid sets are

-{1,1,1,2} because 2 can be measured in multiple ways.{1,1} and {2}. Also 3 can be measured in multiple ways.{1,1,1} and {1,2}

-{1,2,4} though all the weights from 1 to 5 can be measured in unique way but the sum of these weights are not equal to 5.

Your task is to given n calculate the number of different valid measuring stone sets of this grocer.

Input

First line contains T(1≤T≤5000) the number of test cases. Each test case contains 1 integer n in one line. These integers fit in a 32-bit signed integer.

Output

For each test case produce the serial of output followed by the total number of valid measuring stone set as described in the problem statement. This number should fit in a 64-bit signed integer. Look at the output for sample input for details.

Sample Input Output for Sample Input

2 5 223092869

Case 1: 3 Case 2: 7087261

---

Problem setter: Abdullah al Mahmud, Special Thanks: Syed Monowar Hossain