'''
证书拆分的五边形算法
'''

def gen_five(limit):
    sign = -1
    n = 0
    a, b = -1, -1
    while True:
        sign = -sign
        a += 3 * n + 1
        b += 3 * n + 2
        n += 1
        if a < limit:
            yield a, sign
        else:
            break
        if b < limit:
            yield b, sign
        else:
            break

def calc(mod):
    lst = [1, 1]
    while True:
        new = 0
        for exp, sign in gen_five(len(lst)):
            new += lst[exp] * sign
        if not new % mod:
            return len(lst)
        lst.insert(0, new % mod)

print(calc(1000000))