Street Checkers

Alice와 Bob은 새로운 가상 현실 팀 게임인 Street Checkers를 하고 있다. 이 게임은 0부터 10^9까지(양 끝 포함) 번호가 붙은 타일로 나뉜 매우 긴 거리에서 진행된다. 게임이 시작될 때 Alice와 Bob은 0번 타일 위에 서 있고, 구간 [L, R] (양 끝 포함)에서 무작위로 정한 수 X를 받는다. Alice는 홀수 번호 타일로만 점프하고, Bob은 짝수 번호 타일로만 점프한다. 타일의 번호가 X를 나누어떨어뜨리면, 그 타일에 착지한 플레이어는 자신이 좋아하는 색으로 타일을 칠해야 한다. X번 타일이 칠해지면 게임이 끝난다.

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

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어지는 T개의 줄에는 무작위 수 X를 만들 때 쓰는 구간의 시작과 끝인 두 정수 L과 R이 주어진다.

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

• 1 ≤ T ≤ 100.
• 0 ≤ R - L ≤ 10^5.

첫 번째 예제에서 구간 [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이므로 흥미로운 게임이다.