1957E - Carousel of Combinations - CodeForces Solution

from sys import stdin
rd = stdin.readline
t = int(rd())
mod = 10**9 + 7
c = [0,0,1,4,8]
prime = [1] * (10**6+1)
add = [0] * (10**6+1)

for i in range(2, 1000000):
    if prime[i]:
        for j in range(2, 10**6//i + 1):
            prime[i*j] = 0
            add[i*j] = (add[i*j]-1) % mod
            if j % i == 1:
                add[i*j] = (add[i*j]+i) % mod

k = 4
for i in range(5, 10**6+1):
    k = (k+add[i]) % mod
    if prime[i]:
        k = (k+i-1) % mod
    elif i % 8 == 0:
        k = (k-2) % mod
    elif i % 8 == 4:
        k = (k+2) % mod
    c.append((c[-1]+k)%mod)

for _ in range(t):
    n = int(rd())
    print(c[n])