Cho hai số nguyên dương \(l, r\). Hãy tính tổng số lượng bit \(1\) trong biểu diễn nhị phân của các số nguyên trong đoạn từ \(l\) đến \(r\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(q\) (\(q \le 10^5\)) là số truy vấn.
• Trong \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l, r\) (\(1 \le l, r \le 10^{16}\)).

Output

• Gồm \(q\) dòng chứa kết quả của \(q\) truy vấn.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(q = 1, 1 \le l, r \le 10^6\).
• Subtask \(2\) (\(30\%\) số điểm): \(q \le 10^5, 1 \le l, r \le 10^6\).
• Subtask \(3\) (\(40\%\) số điểm): \(q \le 10^5, 1 \le l, r \le 10^{16}\).

Example

3
1 2
2 4
1 10 

2
4
7

7
7 22
3 19
15 17
6 32
2 50
10 11
23 29 

39
38
7
74
135
5
23