hashStuff = {0: 0, 1: 1, 2: 1, 3: 1, 4: 2, 5: 2}

def MEX(S):
    i = 0
    while True:
        if i not in S:
            return i
        i += 1

def P(n):
    if n in hashStuff:
        return hashStuff[n]
    res = Prec(n)
    hashStuff[n] = res
    return res

def Prec(n):
    S = set()
    # Works only for n >= 5
    S.add(P(n-2))
    S.add(P(n-3))
    S.add(P(n-4))
    for i in range(2,n-5+1):
        S.add(nimAdd(P(i),P(n-3-i)))
    return MEX(S)

def nimAdd(x, y):
    return x ^ y

# P(7)
# for i in range(1,1000):
#     print(f"Path, n={i} (oeis={i-1}): {P(i)}")

# Pgames = set()
# for i in range(20000):
#     if hashStuff[i] == 0:
#         Pgames.add(i)

# for i in range(200):
#     print(i, P(1000*i))