시간 제한메모리 제한제출정답맞힌 사람정답 비율
40 초 (추가 시간 없음) 1024 MB1612969.231%

문제

Alice and Bob are playing a new virtual reality team game - Street Checkers. The game is set on an insanely long street divided into tiles which are numbered from 0 to 109(inclusive of both). At the start of the game, Alice and Bob are standing on tile number 0 and are given a random number X in range [LR] (both ends are inclusive). Alice only jumps to odd numbered tiles, while Bob only jumps to even numbered tiles. If the number on the tile divides X, then the player landing on it has to color it with their favorite color. The game is over after tile X has been colored.

A game is considered interesting by both the players if the absolute difference between the number of tiles painted by each is not greater than 2. Help Alice and Bob find how many numbers in the interval [LR] could make for an interesting game.

입력

The first line of the input gives the number of test cases, TT lines follow each containing two integers L and R, the start and end of the interval used to generate the random number X.

출력

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the count of numbers in interval [LR] which results in an interesting game for Alice and Bob.

제한

  • 1 ≤ T ≤ 100.
  • 0 ≤ R - L ≤ 105.

Test Set 1 (13점)

  • 1 ≤ L ≤ R ≤ 106.

Test Set 2 (29점)

  • 1 ≤ L ≤ R ≤ 109.

예제 입력 1

2
5 10
102 102

예제 출력 1

Case #1: 5
Case #2: 1

힌트

For the first sample case, let us look at all the possible number in range [5, 10]:

  • 5 - Alice would paint 2 tiles : {1, 5}, and Bob would not paint any tile. The game would be interesting since the absolute difference is 2.
  • 6 - Alice would paint 2 tiles : {1, 3}, and Bob would paint 2 tiles : {2, 6}. The game would be interesting since the absolute difference is 0.
  • 7 - Alice would paint 2 tiles : {1, 7}, and Bob would not paint any tile. The game would be interesting since the absolute difference is 2.
  • 8 - Alice would paint 1 tile : {1}, and Bob would paint 3 tiles : {2, 4, 8}. The game would be interesting since the absolute difference is 2.
  • 9 - Alice would paint 2 tiles : {1, 3, 9}, and Bob would not paint any tile. The game would not be interesting since the absolute difference is greater than 2.
  • 10 - Alice would paint 2 tiles : {1, 5}, and Bob would paint 2 tiles : {2, 10}. The game would be interesting since the absolute difference is 0.

Thus, the answer for this test case is 5.

In the second sample case, we have only one number 102. Alice would paint 4 tiles : {1, 3, 17, 51} while Bob would paint 4 tiles : {2, 6, 34, 102}. The game would be interesting since the absolute difference is 0.

채점 및 기타 정보

  • 예제는 채점하지 않는다.