Phép OR

Cho $q$ truy vấn. Mỗi truy vấn gồm ba số nguyên dương $a,L,R$.

Yêu cầu: Với mỗi truy vấn, hãy đếm số lượng số nguyên $x$ thỏa mãn:

• $L\le x\le R$;
• $x<mrow><mrow><mi\; mathvariant="normal">O</mi><mi\; mathvariant="normal">R</mi></mrow></mrow>a=x$, trong đó $\mathrm{O}\mathrm{R}$ là phép toán OR theo bit.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $q$ $(1\le q\le {10}^5)$.
• Mỗi dòng trong $q$ dòng tiếp theo chứa ba số nguyên $a,L,R$ $(1\le a\le {10}^9;1\le L\le R\le {10}^9)$.

Dữ liệu ra

Gồm $q$ dòng. Mỗi dòng chứa một số nguyên là đáp án của truy vấn tương ứng.

Ràng buộc

• $1\le q\le {10}^5$.
• $1\le a\le {10}^9$, $1\le L\le R\le {10}^9$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $q\le 2000$; $a,L,R\le 2000$.
• Subtask 2 ($80\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ