思维（Python）

思路：思维。首先我们要知道1到其他点的最短路径是什么？由于题目说了是无向完全图，即每个点都能直达另一个点，所以说直达可能是最短路径。假设直达不是最短路径，说明真正的最短路径之间会经过一些点，那么经过这些点的权重就是(a ^ b) + (b ^ c) + (c ^ d)....根据异或的性质，直达最短路径的权重，即起点值^终点值能够写成(a ^ b) ^ (b ^ c) ^ (c ^ d)...由于同形式的异或和不会大于算术和，因此直达的权重更小，它就是最短路径

并且题目要求把1到其他所有点的最短路径异或值给异或起来，其实就是(1 ^ 1) ^ (1 ^ 2) ^ (1 ^ 3) ^ (1 ^ 4).....写成式子就是(n & 1) ^ reduce(xor, range(1, n + 1))，即n的奇偶性^1到n的异或和。但这样写会超时，本题的n很大，所以说可以把上面的式子打表出来找规律，发现只有4种情况，为n, 0, n + 1, 1，那就直接根据%4的余数来输出答案即可

代码：

import sys

input = lambda: sys.stdin.readline().strip()

import math
inf = 10 ** 18

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LI():
    return input().split()

def LII():
    return list(map(int, input().split()))

def LFI():
    return list(map(float, input().split()))

fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
isqrt = lambda x: int(math.sqrt(x))

'''
n的数据范围小可以写
print((n & 1) ^ reduce(xor, range(1, n + 1)))
'''

def solve():
    n = II()

    tmp = n % 4
    if tmp == 0:
        print(n)
    elif tmp == 1:
        print(0)
    elif tmp == 2:
        print(n + 1)
    else:
        print(1)

# t = 1
t = II()
for _ in range(t):
    solve()