시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (언어별 추가 시간 없음) 1024 MB 47 9 8 50.000%

문제

alt text

필살! 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 ≤ acb < 260)

출력

각 테스트 케이스마다 정답을 한 줄에 하나씩 출력한다.

예제 입력 1

3
3 7 5
1 100 37
11111 99999 55555

예제 출력 1

4
69
62363