Máy tính hỏng

Với hai số nguyên không âm $a$ và $b$, phép cộng $a+b$ và phép XOR nhị phân $a\oplus b$ nói chung cho kết quả khác nhau: phép cộng có nhớ, còn XOR thì không. Chúng chỉ trùng nhau khi việc cộng $a$ với $b$ không sinh ra bất kì lần nhớ nào.

Cho hai số nguyên $l$ và $r$, hãy đếm số cặp có thứ tự $(a,b)$ thoả mãn đồng thời:

• $a+b=a\oplus b$
• $l\le a\le r$
• $l\le b\le r$

Hai cặp $(a,b)$ và $(b,a)$ với $a\ne b$ được tính là hai cặp khác nhau.

Mỗi file dữ liệu chứa nhiều bộ test độc lập.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ ($1\le t\le 100$) — số bộ test.
• $t$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l$ và $r$ ($0\le l\le r\le {10}^9$).

Dữ liệu ra

Với mỗi bộ test, in ra trên một dòng số cặp $(a,b)$ thoả mãn.

Ràng buộc

• $1\le t\le 100$
• $0\le l\le r\le {10}^9$
• Kết quả có thể vượt quá phạm vi số nguyên 32 bit.

Ví dụ