#!/usr/bin/env python3
import subprocess,time
A=10**18
N=500
M=1000000
R=list(range(A,A+N))
bad=bytearray(N)
s=bytearray(b'\x01')*(M+1)
s[0]=s[1]=0
for p in range(2,1001):
  if s[p]:s[p*p::p]=b'\x00'*((M-p*p)//p+1)
for p in range(2,M+1):
  if not s[p]:continue
  h=p>3 and p%3==1 and pow(2,(p-1)//3,p)!=1
  for i in range((-A)%p,N,p):
    e=0
    while R[i]%p==0:R[i]//=p