Truy vấn dãy số

Trong một chuyến khám phá dãy ngân hà xa xôi, FullHouse Dev đã tình cờ bắt gặp một bài toán thú vị về các dãy số nhị phân. Để có thể tiếp tục hành trình, họ cần phải giải quyết bài toán này. Với kinh nghiệm xử lý dữ liệu của mình, FullHouse Dev đã bắt tay vào việc phân tích và giải quyết vấn đề.

Bài toán

Cho \(Q\) truy vấn, mỗi truy vấn gồm ba số \(L\), \(R\) và \(X\). Nhiệm vụ là tìm số lượng số nguyên trong đoạn từ \(L\) đến \(R\) mà có bit thứ \(X\) (tính từ phải qua, bắt đầu từ 1) bằng 1.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(Q\) - số lượng truy vấn
• \(Q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(L\), \(R\) và \(X\)

OUTPUT FORMAT:

• Với mỗi truy vấn, in ra số lượng số nguyên trong đoạn \([L,R]\) thỏa mãn điều kiện đề bài

Ràng buộc:

• \(1 \leq Q \leq 10^5\)
• \(1 \leq L \leq R \leq 10^9\)
• \(1 \leq X \leq 31\)

Ví dụ

INPUT

1
2 6 2

OUTPUT

3

Giải thích

Biểu diễn nhị phân của các số trong đoạn \([2,6]\) như sau:

• 2: 10
• 3: 11
• 4: 100
• 5: 101
• 6: 110

Có 3 số có bit thứ 2 bằng 1 là: 2, 3 và 6. Do đó, kết quả là 3.