prime_distance.py

p_arr=[]
arr=[[0,True,0] for i in range(1000001)]
def preprocess():
    arr[0][1]=False
    arr[1][1]=False
    arr[2][2]=2
    p=2
    
    while(p*p<=1000001):
        #print(p,arr[p][1])
        if(arr[p][1]==True):
            for i in range(p*p,1000001,p):
                arr[i][1]=False
        p+=1
    #Jump for nearest Prime
    prev=2
    for i in range(3,1000001):
        if(arr[i][1]==True):
            prev=i
        arr[i][2]=prev
    #power of 2
    for i in range(20):
        arr[2**i][0]=i
        p_arr.append(2**i)
    prev=1
    for i in range(1000001):
        if(arr[i][0]>0):
            prev+=1
        else:
            arr[i][0]=prev
            
def dp(n):
    #print(n)
    if(n<=2):
        return 0
    else:
        p=arr[n][2]
        diff=p_arr[arr[p][0]]-p
        #print('{}=2**{}-{}'.format(p,arr[p][0],diff))
        return diff+dp(diff)
def main():
        preprocess()
        t=int(input())
        for i in range(t):
            n=int(input())
            sm=dp(n)
            print((sm%1000000007))
if __name__=="__main__":
    main()