Cho số nguyên dương N. Mỗi bước, bạn sẽ biến đổi N thành [N/2], N mod 2, [N/2]. Sau khi thực hiện một cách triệt để, ta thu được một dãy số chỉ toàn số 0 và 1.
Nhiệm vụ của bạn là hãy đếm các số bằng 1 trong đoạn [L, R] của dãy số cuối cùng.
Input:
Dòng đầu tiên là số lượng bộ test T (T ≤ 20).
Mỗi test gồm 3 số nguyên N, L, R (1 ≤ N, L, R < 2^50, 0 ≤ R-L ≤ 100000).
Output:
Với mỗi test, in ra đáp án trên một dòng.
Ví dụ:
Input:
2
7 2 5
10 3 10
Output:
4
5
Giải thích test 1: [7] -> [3, 1, 3] -> [1, 1, 1, 1, 3] -> [1, 1, 1, 1, 1, 1, 1].
Giải thích test 2: Dãy số sau khi biến đổi là [1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1].
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?