3515 - Overflow II 3515 - Overflow II 3515 - Overflow II

Statistics Sub: 17 | AC: 10 | AC%: 58,82 | Score: 4,08
Created by Humberto Díaz Suárez
Added by humbertodiaz (2016-02-06)
Limits
Total Time: 3000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

With UPRM shut down by a strike, Erick and Jai find themselves more bored than ever before. A mutual friend reminds them that they could play Overflow to pass the time.

The game involves two values known as the limit and the counter. Two players choose a positive integer to be the limit. The counter always starts at 1. Players take turns increasing the counter: either doubling it or adding 1 to it. The player who makes the counter greater than the limit loses.

"That game is lame!" complains Erick. It doesn't help that Jai beat him easily last time. Nonetheless, the two settle on having several consecutive games. They will choose two integers A and B beforehand, then use each integer in the range [A, B] as the limit exactly once. Erick will always make the first move.

Assuming that both players pick the best possible moves, how many games will Erick win?
With UPRM shut down by a strike, Erick and Jai find themselves more bored than ever before. A mutual friend reminds them that they could play Overflow to pass the time.

The game involves two values known as the limit and the counter. Two players choose a positive integer to be the limit. The counter always starts at 1. Players take turns increasing the counter: either doubling it or adding 1 to it. The player who makes the counter greater than the limit loses.

"That game is lame!" complains Erick. It doesn't help that Jai beat him easily last time. Nonetheless, the two settle on having several consecutive games. They will choose two integers A and B beforehand, then use each integer in the range [A, B] as the limit exactly once. Erick will always make the first move.

Assuming that both players pick the best possible moves, how many games will Erick win?
With UPRM shut down by a strike, Erick and Jai find themselves more bored than ever before. A mutual friend reminds them that they could play Overflow to pass the time.

The game involves two values known as the limit and the counter. Two players choose a positive integer to be the limit. The counter always starts at 1. Players take turns increasing the counter: either doubling it or adding 1 to it. The player who makes the counter greater than the limit loses.

"That game is lame!" complains Erick. It doesn't help that Jai beat him easily last time. Nonetheless, the two settle on having several consecutive games. They will choose two integers A and B beforehand, then use each integer in the range [A, B] as the limit exactly once. Erick will always make the first move.

Assuming that both players pick the best possible moves, how many games will Erick win?

Input specification

The input will begin with a single line consisting of an integer T (1 ≤ T ≤ 5000) denoting the number of test cases that will follow. Each test case will consist of a single line with two integers A and B (1 ≤ A ≤ B ≤ 1018), the first limit and the last limit for the rounds of Overflow.
The input will begin with a single line consisting of an integer T (1 ≤ T ≤ 5000) denoting the number of test cases that will follow. Each test case will consist of a single line with two integers A and B (1 ≤ A ≤ B ≤ 1018), the first limit and the last limit for the rounds of Overflow.
The input will begin with a single line consisting of an integer T (1 ≤ T ≤ 5000) denoting the number of test cases that will follow. Each test case will consist of a single line with two integers A and B (1 ≤ A ≤ B ≤ 1018), the first limit and the last limit for the rounds of Overflow.

Output specification

The output will consist of one line per test case indicating the number of the test case and the number of rounds that Erick will win for the given range of limits. See the example below for the precise format to be used. Assume that Jai and Erick play optimally.
The output will consist of one line per test case indicating the number of the test case and the number of rounds that Erick will win for the given range of limits. See the example below for the precise format to be used. Assume that Jai and Erick play optimally.
The input will begin with a single line consisting of an integer T (1 ≤ T ≤ 5000) denoting the number of test cases that will follow. Each test case will consist of a single line with two integers A and B (1 ≤ A ≤ B ≤ 1018), the first limit and the last limit for the rounds of Overflow.

Sample input

2
1 5
5 10

Sample output

Case #1: 1
Case #2: 2

Hint(s)

The first case has Erick winning when the limit is 2. He loses the rounds where the limit is 1, 3, 4, or 5. In the second case, Erick wins when the limit is 8 or 10.
The first case has Erick winning when the limit is 2. He loses the rounds where the limit is 1, 3, 4, or 5. In the second case, Erick wins when the limit is 8 or 10.
The first case has Erick winning when the limit is 2. He loses the rounds where the limit is 1, 3, 4, or 5. In the second case, Erick wins when the limit is 8 or 10.

Recommendation

We have carefully selected several similar problems: 3675 | 3377 | 2441 | 1960 | 3091 | 3361