Josephus Permutation

Time Limit: 1 sec

 

The Problem

Dola  is crazy about  mathematics . Recently she have learnt  Josephus permutation .  You know about  Josephus permutation? It is a theoretical problem related to a certain counting out  game. There is a story behind this game .The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. According to Josephus' account of the siege of Yodfat, he and his 40 soldiers were trapped in a cave by Roman soldiers. They chose suicide over capture. They made a plan. They stood in a circular way. The counting out begins at any point in the circle and proceeds around the circle in a fixed direction. In each step, the pointed person will be skipped and the next person will commit  suicide. These steps proceed around the circle until only the last person remains. That means if there are 4 people in a circle and the counting starts from 1st position then 2nd, 4th and 3rd soldiers will commit to suicide sequentially and at last 1st person will survive. Josephus states that by luck or possibly by the hand of God, he and another man remained until the end and surrendered to the Romans rather than killing themselves.”

 

By the way, Dola found this very interesting. She is thinking about which is the position of the last alive man if the starting position always be 1? Suppose if there is 14 man in that circle, 13 number  positioned man can be survived.

 

Now she is busy with an interesting thing. She wants to know how much safer a position is if anyone wants to survive for various range of circle. Example: if  a circle is made of 1, 2 3 & 4 persons then 1,1,3 & 1 positions are the survival positions respectively.

 

Now she wants your help . She will give you a range of person number A & B . Your task is to find out which position will repeat most as survival position. If there is more than one print the maximum position among them. 

 

The Input

Input starts with an integer T that denotes the number of test cases.

Each case have three inputs A, B.

 

Constraints

1 <= T <=100

1<= ( A <=B ) <= 10^18

 

The Output

For each test case print the case number and the most repeated survival position in the given range A - B as the following format “Case X: Y” where X is the case number starts from 1 and Y is the desired answer.  Check the samples for further clarification.

 

Sample Input

2

1 4

2 5

 

Sample Output

Case 1: 1

Case 2: 3

Note

For test case 2:

A= 2, B= 5

In a circle of 2 people the survival position number is 1

In a circle of 3 people the survival position number is 3

In a circle of 4 people the survival position number is 1

In a circle of 5 people the survival position number is 3

Both 1st and 3rd position repeated 2 times as survival position. So answer is 3 (maximum of 1 and 3) 

 

 

Inter University Programming Contest(II) - 2018 [BGC Trust University Bangladesh]

Problem Setter: Hafiz Al Asad