def sieve1(N):
    M = (N-3)//2+1
    n = int(N**0.5)
    P = [True,True,True,False,True,True,False,True,True,False,True,False,False,True]+[False]*(M-15)
    G = (6,4,2,4,2,4,6)
    last = 30*(N//30)+1
    for w in range(31,last,30):
        P[(w-3)//2]=True
        x = w
        for g in G:
            x+=g
            P[(x-3)//2]=True
    P[(last-3)//2]=True
    for g in G:
        last+=g
        if last>N:
            break
        P[(last-3)//2]=True
    for i in range(7,n+1,2):
        if P[(i-3)//2]:
            for j in range((i**2-3)//2,M-1,i):
                P[j]=False
    return [2]+[2*i+3 for i in range(len(P)) if P[i]]

ZGVmIHNpZXZlMShOKToKICAgIE0gPSAoTi0zKS8vMisxCiAgICBuID0gaW50KE4qKjAuNSkKICAgIFAgPSBbVHJ1ZSxUcnVlLFRydWUsRmFsc2UsVHJ1ZSxUcnVlLEZhbHNlLFRydWUsVHJ1ZSxGYWxzZSxUcnVlLEZhbHNlLEZhbHNlLFRydWVdK1tGYWxzZV0qKE0tMTUpCiAgICBHID0gKDYsNCwyLDQsMiw0LDYpCiAgICBsYXN0ID0gMzAqKE4vLzMwKSsxCiAgICBmb3IgdyBpbiByYW5nZSgzMSxsYXN0LDMwKToKICAgICAgICBQWyh3LTMpLy8yXT1UcnVlCiAgICAgICAgeCA9IHcKICAgICAgICBmb3IgZyBpbiBHOgogICAgICAgICAgICB4Kz1nCiAgICAgICAgICAgIFBbKHgtMykvLzJdPVRydWUKICAgIFBbKGxhc3QtMykvLzJdPVRydWUKICAgIGZvciBnIGluIEc6CiAgICAgICAgbGFzdCs9ZwogICAgICAgIGlmIGxhc3Q+TjoKICAgICAgICAgICAgYnJlYWsKICAgICAgICBQWyhsYXN0LTMpLy8yXT1UcnVlCiAgICBmb3IgaSBpbiByYW5nZSg3LG4rMSwyKToKICAgICAgICBpZiBQWyhpLTMpLy8yXToKICAgICAgICAgICAgZm9yIGogaW4gcmFuZ2UoKGkqKjItMykvLzIsTS0xLGkpOgogICAgICAgICAgICAgICAgUFtqXT1GYWxzZQogICAgcmV0dXJuIFsyXStbMippKzMgZm9yIGkgaW4gcmFuZ2UobGVuKFApKSBpZiBQW2ldXQ==