Pigeon SSNA want to build a tower with some wood walls. Let's describe the tower they want to make:

1. A Tower can consist of different number of level.
2. If a tower contain L levels then 1^st level must contain L holes, 2^nd level L-1, 3^rd level L-2 ….. L level contain 1 hole.
3. Each room contain 3 wood walls.

See the picture below:

3 Level Tower	4 Level tower

Now pigeon SSNA has n wood walls. What is maximum number of level he can made.

Input

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

Each case starts with a line containing an integer n (1 ≤ n ≤ 10¹²)

Output

For each case of input you have to print the case number and expected answer.

Example

Input:
2
15
24
Output:
Case 1: 3
Case 2: 4