Medium Beginners Problems > Ad-hoc

Shooting Game is a very dangerous game. There are **N** persons who stand forming a circle. Everyone has a unique ID number **(1 to N)**. They stand in there serially clockwise. Another man with a gun stands in the center of that circle. He starts shooting one by one in clock wise direction. But there are some rules. He doesn't shoot two consecutive alive person. He always starts from the person with ID 1. On starting round, ID 1 survives ID 2 dies ID 3 survives ID 4 dies ID 5 survives and the so on. The game continues until only one person survives. Like for **N = 10**, the Shooting order will be **2 -> 4 -> 6 -> 8 -> 10 -> 3 -> 7 -> 1 -> 9** and the person with ID 5 is set to free. Consider a function **F(N)** which takes the number of the persons (excluding the shooter) as parameter and returns the ID of the person who survives in the end. Mr. Sifat Shishir, a famous mathematician wonders, given a range **A** to **B** (inclusive), how many integers are there for which **F(N) = N/2**. Input: ------ First line of input consists of one integer **T (T<=10^4)**, that denotes the number of test case. Then next T lines follow. Each line have two integers **A** & **B**. **( 1 <=A <= B <= 10^18)** Output: ------- For each test case print a line "**Case t: C**" without quotes where t is the case number and C is the number of integers for which **F(N) = N/2** Sample Input ------------ 2 1 5 1 10 Sample Output ------------- Case 1: 1 Case 2: 2

Md. Samiul Alam