Nguoingu45 là một người rất đam mê lập trình và đặc biệt thích truyền bá lan rộng lập trình thi đấu đến mọi người. Hôm nay Nguoingu45 thử thách các đồng môn sư đệ của mình bằng một câu hỏi rất đơn giản: cho hai số \(L\) và \(R\), tổng XOR của đoạn \([L,R]\) là bao nhiêu?.

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) \((1 \lt T \lt 10^5)\) - số câu hỏi
• Dòng thứ \(i\) trong \(T\) dòng tiếp theo chứa hai số nguyên dương \(L, R\) \((1 \le L \le R \le 2^{63})\) thể hiện một câu hỏi

Output

• In ra \(T\) dòng lần lượt là đáp án của các câu hỏi theo thứ tự nhập vào.

Scoring

• Subtask 1 (20 điểm): \(1 \le l \le r \le 1000\)
• Subtask 2 (30 điểm): \(1 \le l \le r \le 10^6\)
• Subtask 3 (50 điểm): Không có điều kiện gì thêm.

Sample Input 1

1
4 8

Sample Output 1 8

Notes

• Tổng XOR của đoạn \([4,8] = 4 \oplus 5 \oplus 6 \oplus 7 \oplus 8 = 8\)