Tính \(1 \oplus 2 \oplus 3 \oplus \dots \oplus n\) với \(n\) được nhập từ bàn phím.

Input

• Dòng 1 chứa \(t\) \((t \leq 10^5)\) - số câu hỏi.
• \(t\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(n\).

Output

• Ứng với mỗi câu hỏi in ra đáp án cần tìm.

Constraints

• Subtask 1 [10%]: \(n \le 10\);
• Subtask 2 [90%]: \(n \le 10^{12}\).

Example

2
3
6

0
7

Note

• Nguồn: SPOJ