NAJFDB - Find out Defect Ball
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
Added by: | Najmuzzaman |
Date: | 2014-10-25 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |