어디에나 있는 님 게임
시간 제한2초메모리 제한512 MB
님 위치 (N, 2N, 3N)이 첫 번째 플레이어의 승리, 즉 N xor 2N xor 3N이 0이 아닌 N을 [L, R] 범위에서 센다.
문제
이 게임은 정말 질리도록 나온다. 님은 두 사람이 번갈아 가며 서로 다른 더미에서 물건을 가져가는 수학적 전략 게임이다. 각 차례에 플레이어는 물건을 최소 하나 가져가야 하며, 같은 더미에 있는 한 원하는 만큼 가져갈 수 있다. 마지막 물건을 가져간 플레이어가 이긴다.
이 문제에서는 더미가 3개뿐이고, 초기 상태도 특별해서 항상 (N, 2 × N, 3 × N) 형태이다. 여기서 N은 양의 정수이다. 예를 들어 N이 3이면 세 더미는 각각 3, 6, 9개의 물건으로 시작한다.
승리 상태란, 지금 차례인 플레이어가 상대가 무엇을 하든 이길 수 있는 전략이 항상 존재하는 더미 상태를 말한다.
이 문제에서 두 정수 L과 R이 주어진다. 위에서 설명한 대로 N으로 초기 상태를 만들었을 때, 선공 플레이어에게 승리 상태가 되는 서로 다른 N (L ≤ N ≤ R)의 개수를 구하시오.
입력
프로그램은 하나 이상의 테스트 케이스에 대해 채점된다. 입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 T (1 ≤ T ≤ 105)가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.
각 테스트 케이스는 공백으로 구분된 두 정수 L과 R (1 ≤ L ≤ R ≤ 261)을 포함하는 한 줄이다. 이 범위는 위에서 설명한 것과 같다.
출력
각 테스트 케이스마다 위에서 설명한 조건을 만족하는 서로 다른 N의 개수를 한 줄에 출력한다.
힌트
첫 번째 테스트 케이스에서 승리 상태를 만드는 N은 3뿐이며, 그 상태는 (3, 6, 9)이다.