def factor(num, ans = 2):
    if num%2 == 0:
        res = {2}
        while num%2 == 0:
            num //= 2
    else:
        res = set()
    d = 3
    while num >= d*d:
        if d%5 and num%d == 0:
            res.add(d)
            while num%d == 0:
                num //= d 
        d += 2 
    if num>1:
        res.add(num)
 
    return res
 
b = set()
for i in range(2,400001):
    a = factor(i)
    #print(i, a)
    #j = i
print('end')

ZGVmIGZhY3RvcihudW0sIGFucyA9IDIpOgogICAgaWYgbnVtJTIgPT0gMDoKICAgICAgICByZXMgPSB7Mn0KICAgICAgICB3aGlsZSBudW0lMiA9PSAwOgogICAgICAgICAgICBudW0gLy89IDIKICAgIGVsc2U6CiAgICAgICAgcmVzID0gc2V0KCkKICAgIGQgPSAzCiAgICB3aGlsZSBudW0gPj0gZCpkOgogICAgICAgIGlmIGQlNSBhbmQgbnVtJWQgPT0gMDoKICAgICAgICAgICAgcmVzLmFkZChkKQogICAgICAgICAgICB3aGlsZSBudW0lZCA9PSAwOgogICAgICAgICAgICAgICAgbnVtIC8vPSBkIAogICAgICAgIGQgKz0gMiAKICAgIGlmIG51bT4xOgogICAgICAgIHJlcy5hZGQobnVtKQogICAgCiAgICByZXR1cm4gcmVzCiAgICAKYiA9IHNldCgpCmZvciBpIGluIHJhbmdlKDIsNDAwMDAxKToKICAgIGEgPSBmYWN0b3IoaSkKICAgICNwcmludChpLCBhKQogICAgI2ogPSBpCnByaW50KCdlbmQnKQ==

YWFhYWJiY2FhCgo=

aaaabbcaa