Mod, Xor and Everything

You are given an integer $ n $.

You are required to calculate $\text {(n mod 1) xor (n mod 2) xor ... xor (n mod (n - 1)) xor (n mod n). } $

The “ $ xor $ ” operation means “exclusive OR”.

The first line contains an integer $ T \left(1 \leq T \leq 5 \right) $ representing the number of test cases.

For each test case, there is an integer $ n \left(1\leq n\leq 10^{12}\right) $ in one line.

For each test case, print the answer in one line.

5
1
2
3
4
5

0
0
1
1
2

2017中国大学生程序设计竞赛-杭州站-重现赛（感谢浙江理工）