필살! 60단 컴보
시간 제한2초메모리 제한1024 MB
각 질의 (a, b, c)마다 a 이상 b 이하인 이진수 x 중에서 60개 음 콤보 게임에서 c보다 높은 점수를 내는 것의 개수를 센다. 콤보 X에서 GOOD 판정은 2X-1점을 준다.
문제
필살! 60단 컴보는 성모가 개발한 리듬 게임이다. 이 게임에서 곡은 언제나 60개의 노트로 이루어져 있으며, 각 노트에 대한 판정은 GOOD(1)과 MISS(0)밖에 없다. 모든 리듬 게임이 그러하듯 필살! 60단 컴보에도 콤보 시스템이 존재한다. GOOD 판정을 받았을 때 기본적으로 얻는 점수는 1점이지만, 콤보가 쌓일 때마다 2점씩 추가된다. 다시 말해, GOOD 판정을 받은 시점의 콤보가 X라면, 2X-1점을 얻는다. MISS 판정을 받으면 콤보가 초기화되며, 점수를 받지 못한다. 예를 들면, 노트 5개를 친 결과가 11101이라면, 점수는 1 + 3 + 5 + 0 + 1 = 10이다.
모든 플레이어의 플레이 기록은 서버에 저장된다. 이때, 60개의 노트를 친 결과를 2진법으로 읽은 수 하나가 서버로 올라가게 된다. 예를 들면, 마지막 4개의 노트에서만 GOOD 판정을 받고 나머지 판정이 모두 MISS인 경우, 이 플레이를 나타내는 수는 1111(2) = 15이다. 성모는 오랜 작업 끝에 서버의 랭킹 시스템의 개발을 완료했고, 테스트 단계만 남은 상황이다. 많은 사람들의 플레이 기록들을 잘 처리할 수 있는지 확인하기 위해, 성모는 a부터 b까지의 플레이 기록을 모두 하나씩 서버에 전송한 뒤, 그중에서 플레이 기록이 c인 사람이 몇 등인지 확인하는 테스트 데이터를 만들었다. 하지만 실제로 몇 등이어야 하는지를 채워 넣지 못했다. 성모를 도와 테스트 데이터를 완성해보자!
등수는 (나보다 높은 점수를 가진 사람 수) + 1로 정의된다. 예를 들면, 5명의 점수가 각각 3점, 2점, 2점, 1점, 1점이라면 3점은 1등, 2점 두 명은 2등, 1점 두 명은 4등이다.
입력
첫 번째 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 300,000)
다음 T개의 줄에 걸쳐 각 줄에 정수 a, b, c가 주어진다. (0 ≤ a ≤ c ≤ b < 2^60)
출력
각 테스트 케이스마다 정답을 한 줄에 하나씩 출력한다.