거리 체커

Alice와 Bob은 새로운 가상 현실 팀 게임인 거리 체커를 하고 있다. 게임은 타일로 나뉜 매우 긴 거리를 배경으로 하며, 타일에는 0부터 $10^{9}$까지(양 끝 포함) 번호가 매겨져 있다. 게임을 시작할 때 Alice와 Bob은 번호가 0인 타일에 서 있으며, [L, R] 범위(양 끝 포함)의 무작위 수 X가 주어진다. Alice는 홀수 번호의 타일로만 점프하고, Bob은 짝수 번호의 타일로만 점프한다. 타일의 번호가 X를 나누어떨어지게 하면, 그 타일에 착지한 플레이어는 자신이 가장 좋아하는 색으로 타일을 칠해야 한다. 타일 X가 칠해지면 게임이 끝난다.

각 플레이어가 칠한 타일 수의 절댓값 차이가 2보다 크지 않으면 두 플레이어 모두 이 게임을 흥미롭다고 여긴다. Alice와 Bob이 구간 [L, R]에서 흥미로운 게임이 되게 할 수 있는 수가 몇 개인지 구하도록 도와주자.

제한

테스트 세트당 시간 제한: 40초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 0 ≤ R - L ≤ $10^{5}$.

테스트 세트 1 (공개)

1 ≤ L ≤ R ≤ $10^{6}$.

테스트 세트 2 (비공개)

1 ≤ L ≤ R ≤ $10^{9}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어지는 T개의 줄에는 각각 무작위 수 X를 생성하는 데 사용되는 구간의 시작과 끝인 두 정수 L과 R이 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y는 Alice와 Bob에게 흥미로운 게임이 되는 구간 [L, R]의 수의 개수이다.

첫 번째 예제 케이스에서는 범위 $[5, 10]$에 있는 가능한 모든 수를 살펴보자.

• 5 - Alice는 2개의 타일, 즉 {1, 5}을 칠하고, Bob은 어떤 타일도 칠하지 않는다. 절댓값 차이가 2이므로 게임은 흥미롭다.

• 6 - Alice는 2개의 타일, 즉 {1, 3}을 칠하고, Bob은 2개의 타일, 즉 {2, 6}을 칠한다. 절댓값 차이가 0이므로 게임은 흥미롭다.

• 7 - Alice는 2개의 타일, 즉 {1, 7}을 칠하고, Bob은 어떤 타일도 칠하지 않는다. 절댓값 차이가 2이므로 게임은 흥미롭다.

• 8 - Alice는 1개의 타일, 즉 {1}을 칠하고, Bob은 3개의 타일, 즉 {2, 4, 8}을 칠한다. 절댓값 차이가 2이므로 게임은 흥미롭다.

• 9 - Alice는 2개의 타일, 즉 {1, 3, 9}을 칠하고, Bob은 어떤 타일도 칠하지 않는다. 절댓값 차이가 2보다 크므로 게임은 흥미롭지 않다.

• 10 - Alice는 2개의 타일, 즉 {1, 5}을 칠하고, Bob은 2개의 타일, 즉 {2, 10}을 칠한다. 절댓값 차이가 0이므로 게임은 흥미롭다.

따라서 이 테스트 케이스의 답은 5이다.

두 번째 예제 케이스에는 수 102 하나만 있다. Alice는 4개의 타일, 즉 {1, 3, 17, 51}을 칠하고, Bob은 4개의 타일, 즉 {2, 6, 34, 102}을 칠한다. 절댓값 차이가 0이므로 게임은 흥미롭다.