def sieve(N):
    M = (N-3)//2+1
    n = int(N**0.5)
    P = [3,5,7,0,11,13,0,17,19,0,23,0,0,29,31,0,0,37,0,41,43,0,47,
         0,0,53,0,0,59,61,0,0,67,0,71,73,0,0,79,0,83,0,0,89,0,0,0,
         97,0,101,103,0,107,109,0,113,0,0,0,121,0,0,127,0,131,0,0,
         137,139,0,143,0,0,149,151,0,0,157,0,0,163,0,167,169,0,173,
         0,0,179,181,0,0,187,0,191,193,0,197,199,0,0,0,0,209]+[0]*(M-105)
    G = (10,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2)
    last = 210*(N//210)+1
    for w in range(211,last,210):
        P[(w-3)//2]=1
        x = w
        for g in G:
            x+=g
            P[(x-3)//2]=1
    for g in G:
        P[(last-3)//2]=1
        last+=g
        if last > N:
            break
    for i in range(11,n+1,2):
        if P[(i-3)//2]:
            for j in range((i**2-3)//2,M-1,i):
                P[j]=0
    return [2]+[2*i+3 for i in range(len(P)) if P[i]]

ZGVmIHNpZXZlKE4pOgogICAgTSA9IChOLTMpLy8yKzEKICAgIG4gPSBpbnQoTioqMC41KQogICAgUCA9IFszLDUsNywwLDExLDEzLDAsMTcsMTksMCwyMywwLDAsMjksMzEsMCwwLDM3LDAsNDEsNDMsMCw0NywKICAgICAgICAgMCwwLDUzLDAsMCw1OSw2MSwwLDAsNjcsMCw3MSw3MywwLDAsNzksMCw4MywwLDAsODksMCwwLDAsCiAgICAgICAgIDk3LDAsMTAxLDEwMywwLDEwNywxMDksMCwxMTMsMCwwLDAsMTIxLDAsMCwxMjcsMCwxMzEsMCwwLAogICAgICAgICAxMzcsMTM5LDAsMTQzLDAsMCwxNDksMTUxLDAsMCwxNTcsMCwwLDE2MywwLDE2NywxNjksMCwxNzMsCiAgICAgICAgIDAsMCwxNzksMTgxLDAsMCwxODcsMCwxOTEsMTkzLDAsMTk3LDE5OSwwLDAsMCwwLDIwOV0rWzBdKihNLTEwNSkKICAgIEcgPSAoMTAsMiw0LDIsNCw2LDIsNiw0LDIsNCw2LDYsMiw2LDQsMiw2LDQsNiw4LDQsMiw0LDIsNCw4LDYsNCw2LDIsNCw2LDIsNiw2LDQsMiw0LDYsMiw2LDQsMiw0LDIsMTAsMikKICAgIGxhc3QgPSAyMTAqKE4vLzIxMCkrMQogICAgZm9yIHcgaW4gcmFuZ2UoMjExLGxhc3QsMjEwKToKICAgICAgICBQWyh3LTMpLy8yXT0xCiAgICAgICAgeCA9IHcKICAgICAgICBmb3IgZyBpbiBHOgogICAgICAgICAgICB4Kz1nCiAgICAgICAgICAgIFBbKHgtMykvLzJdPTEKICAgIGZvciBnIGluIEc6CiAgICAgICAgUFsobGFzdC0zKS8vMl09MQogICAgICAgIGxhc3QrPWcKICAgICAgICBpZiBsYXN0ID4gTjoKICAgICAgICAgICAgYnJlYWsKICAgIGZvciBpIGluIHJhbmdlKDExLG4rMSwyKToKICAgICAgICBpZiBQWyhpLTMpLy8yXToKICAgICAgICAgICAgZm9yIGogaW4gcmFuZ2UoKGkqKjItMykvLzIsTS0xLGkpOgogICAgICAgICAgICAgICAgUFtqXT0wCiAgICByZXR1cm4gWzJdK1syKmkrMyBmb3IgaSBpbiByYW5nZShsZW4oUCkpIGlmIFBbaV1d