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


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


def P(n: int) -> int:
    """
    Compute nimber for a path of a certain length
    """
    if n in hashStuff:
        return hashStuff[n]
    res = Prec(n)
    hashStuff[n] = res
    return res


def Prec(n: int) -> int:
    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: int, y: int) -> int:
    return x ^ y