Medium Search Techniques > Binary Search/Bisection

Our Lazy Arnab and his wife “you know who” is gone for shopping and they have told their son, “Why I am “ to take care of his little sister “What is that”. “Why I am” is a naughty boy and always up to trouble his little sister. Little “What is that” have some coins and from them naughty “Why I am” replaces one coin with another faulty coin which weight is different from all other coins and all other coins have same weight. Little “What is that” has a balance and from that she can compare any equal numbers of coin. Can you tell us how many operations little “What is that” need to perform to find the faulty coin. Input: ------ The first line contains an integer T( 1<= T <= 10000 ) which denotes the number of Test cases. T test cases follow . Each test case contains a integer number N ( 2 < N <= 10000 ) which denotes number of coins little "What is that" have. Output: ------- For each test case, print a line “Case x: y” where x is replaced by the test case number and y is the minimum number of balance check little “What is that” need to be performed in order to find the faulty coin. Constraints: ------- 1 <= T <= 10000 3 <= N <= 10000 Sample Input ------------ 1 3 Sample Output ------------- Case 1: 2

Shakil Ahmed