You have N balls and a scale (Daripalla). There is one ball which has a defect that causes it to weigh less than other balls. Your task is find the defect ball with minimum weighings using the scale.

Suppose you have 8 balls. You can find out the defect ball using only 2 weighings.

At first you devide the balls into 3 groups 3, 3 and 2.

Weighing 1: Check the weight of first 2 two groups: 3 and 3.

If their weight is same

{

then we are sure defect in third group.

Weighing 2: Now check the last 2 ball. And reach to our goal.

}

Otherwise their weight are not the same then defect on loss weight side.

{

Then select he defect side 3 ball and split it again into 3 groups 1, 1 and 1

Weighing 2: check weight the first 2 groups.

If their weight is same then defect ball is third one.

Otherwise we found the defect ball on first part.

}

Input

The first line of the input contains an integer T (T ≤ 100000) denoting the number of test cases. Each test case contains Number of ball N. 1 ≤ N ≤ 10^9.

Output

For each case, print the case number and print the minimum step .

Example

Input:
2
8
12

Output:
Case 1: 2
Case 2: 3