Mahbub, Emon and Mizan are three brothers. Mahbub is the oldest brother, Emon is the second oldest and Mizan is the youngest. Now they come to their uncle for "EID SALAMI". But they decided that the older one will strictly get more money than the younger. But their uncle has another plan. He told them that he will give them an amount of money and they have to tell them how many ways they can collect money so that the elder gets more money than the younger and they have to take all the money. As they have to meet with other cousin's so they come to you, as they know that you are a great programmer, and if you can solve their problem they will give some SALAMI :)

Input

Input starts with an integer T (≤ 500), denoting the number of test cases.

Each case starts with a line containing an integer M. M denotes the amount of money their uncle wants to give them. 6 ≤ M ≤ 1000000.

Output

For each case, print the case number and the total number of ways. See the samples for exact formatting.

Example

Input:
2
40
12

Output:
Case 1: 114
Case 2: 7

Problem Setter: Asif Mujtaba
Used in Eid 2016 contest.
More about Eid 2016 contest: Click Here.