Cho \(q\) truy vấn, mỗi truy vấn gồm \(3\) số nguyên dương \(a, l, r\) , yêu cầu tính số lượng số \(x\) sao cho:

• \(l \le x \le r\)
• \(x\) or \(a = x\)

Bạn có thể tham khảo phép or tại đây

Input

• Dòng đầu tiên là số \(q\) \((1 \le q \le 10^5)\).
• \(q\) dòng tiếp theo, mỗi dòng là \(3\) số \(a, l, r\) \((1 \le a, l, r \le 10^9)\).

Output

• Gồm \(q\) dòng, mỗi dòng là đáp án cho \(1\) truy vấn.

Scoring

Subtask \(1\) (\(20\%\) số điểm): Có \(1 \le q \le 2000\), \(1 \le a, l, r \le 2000\).
Subtask \(2\) (\(80\%\) số điểm): Không có ràng buộc gì thêm

Example

1
1 2 5

2