비트문자열

어떤 양의 정수 $K$에 대해 길이가 $2^K$인 비트문자열 $X$가 있다. $X$의 비트들은 왼쪽부터 순서대로 $1$번부터 $2^K$번까지 번호가 붙어 있다. 처음에 $X$의 모든 비트는 $0$이다.

다음과 같은 함수 $f(x)$가 있다. 이때, $x$는 길이가 $2^k$ 꼴인 비트문자열이다.

1. $x$의 길이가 $1$인 경우, 아무 작업 없이 종료한다.
2. $x$를 절반으로 나눈다. 왼쪽 절반을 $l$, 오른쪽 절반을 $r$이라고 하자.
3. 왼쪽 절반 $l$의 비트를 뒤집는다.
4. $f(l)$을 재귀호출 한다.
5. $f(r)$을 재귀호출 한다.

여기서, 비트를 뒤집는다는 것은 $0$은 $1$로 만들고, $1$은 $0$으로 만든다는 것을 의미한다.

모든 비트가 $0$인 길이가 $2^K$인 비트문자열 $X$에서 $f(X)$를 호출한 이후 비트문자열 $X$를 $S_K$라고 하자.

$K = 1$인 경우, 초기 비트문자열은 $00$이다. 위 작업의 결과로 최종 비트문자열은 $10$이 된다. (왼쪽 절반인 $0$이 $1$로 바뀌었다.)

$K = 2$인 경우, 초기 비트문자열은 $0000$이다. 위 작업에서 첫 번째 호출이 비트문자열을 $1100$으로 바꾼다. 첫 번째 호출에서 4번 과정의 재귀호출을 하면 비트문자열이 $0100$으로 바뀌고, 5번 과정의 재귀호출을 하면 비트문자열은 $0110$으로 바뀌므로, 최종 비트문자열은 $0110$이 된다.

$K = 3$인 경우, 이와 마찬가지로 최종 비트문자열은 $10010110$이 된다.

정리하면 다음과 같다.

양의 정수 $K$, $L$, $R$를 입력으로 받아, $S_K$의 $L$번 비트부터 $R$번 비트까지 $1$의 개수를 구하는 프로그램을 작성하시오.

입력 형식

첫 줄에 테스트 케이스의 수를 나타내는 정수 $T$가 주어진다. ($1 \le T \le 200\,000$)

각 테스트 케이스의 첫 줄에 양의 정수 $K$, $L$, $R$이 공백으로 구분되어 주어진다. ($1 \le K, L, R \le 1\,000\,000\,000\,000\,000\,000;$ $L \le R \le 2^{K}$)

출력 형식

각 테스트 케이스에 대해, $S_K$의 $L$번 비트부터 $R$번 비트까지 $1$의 개수를 각 줄에 출력한다.

예제

3
2 2 4
3 1 6
4 3 6

2
3
2

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설