Chef Vivek is good in mathematics and likes solving problems on prime numbers. One day his friend Jatin told him about Victory numbers. Victory number can be defined as a number formed after summing up all the prime numbers till given number n. Now, chef Vivek who is very fond of solving questions on prime numbers got busy in some other tasks. Your task is to help him finding victory number.

-----Input:-----
- First line will contain $T$, number of test cases. Then the test cases follow. 
- Each test case contains of a single line of input $N$ till which sum of all prime numbers between 1 to n has to be calculated.

-----Output:-----
For each test case, output in a single line answer to the victory number.

-----Constraints-----
- $1 <= T <= 1000$
- $1 <= N <= 10^6$

-----Sample Input:-----
3
22
13
10

-----Sample Output:-----
77
41
17

Difficulty: interview

Starter code:

Solutions:
from math import sqrt 

test = int(input())
for i in range(test):
 sum = 0
 max = int(input())
 if max==1:
  sum = 0
 elif max==2:
  sum += 2
 else:    
  sum = sum + 2
  for x in range(3,max+1):
   half = int(sqrt(x)) + 1
   if all(x%y!=0 for y in range(2,half)):
    sum = sum + x
 print(sum) 

# cook your dish here
def primes(n):
 prime=[True]*(n+1)
 p=2
 while(p*p<=n):
  if(prime[p]==True):
   i=p*2
   while(i<=n):
    prime[i]=False
    i+=p
  p+=1
 sum=0
 for i in range(2,n+1):
  if(prime[i]):
   sum+=i
 return sum
t=int(input())
for i in range(t):
 n=int(input())
 print(primes(n))




pr=[1]*(10**6+1)
pr[0]=pr[1]=0
for i in range(2,10**6+1):
 if pr[i]:
  for j in range(i*i,10**6+1,i):
   pr[j]=0
ans=[0]
for i in range(1,10**6+1):
 if pr[i]:
  ans.append(ans[-1]+i)
 else:
  ans.append(ans[-1])
 
t=int(input())
for _ in range(t):
 n=int(input())
 print(ans[n])


for i in range(int(input())):
 a = int(input())
 l = []
 for num in range(2,a + 1):  
  if num > 1:  
   for i in range(2,int(num**.5)+1):  
    if (num % i) == 0:  
     break 
   else:  
    l.append(num)
 print(sum(l))

def sieve(x):
 p = [1]*(x+1)
 p[0] = 0
 p[1] = 0
 
 t = 2
 while(t**2 < x):
  if p[t] == 1:
   for j in range(t**2, x+1, t):
    p[j] = 0
  t += 1
 
 return p

l = sieve(10**6 +2)
s = [0]

for i in range(1, len(l)):
 if l[i] == 1:
  s.append(s[i-1] + i)
 else:
  s.append(s[i-1])


for u in range(int(input())):
 x = int(input())
 print(s[x])

def prime(n):
 if (n <= 1):
  return False
 if (n <= 3):
  return True
 if (n % 2 == 0 or n % 3 == 0):
  return False

 i = 5
 while (i * i <= n):
  if (n % i == 0 or n % (i + 2) == 0):
   return False
  i = i + 6

 return True

for _ in range(int(input())):
 n = int(input())
 summ = 0
 for i in range(1,n+1):
  if prime(i):
   summ += i
 print(summ)


def isPrime(n) : 
 
 if (n <= 1) : 
  return False
 if (n <= 3) : 
  return True
 if (n % 2 == 0 or n % 3 == 0) : 
  return False
 i = 5
 while(i * i <= n) : 
  if (n % i == 0 or n % (i + 2) == 0) : 
   return False
  i = i + 6
 return True

def printPrime(n):
 s=0
 for i in range(2, n + 1):
  if isPrime(i):
   s=s+i
 print(s)
t=int(input())
for i in range(t):
 n = int(input())
 printPrime(n) 




from math import sqrt
t = int(input())
for _ in range(t):
 n=int(input())
 sum= 0
 if n<2:
  pass
 elif n==2:
  sum= 2
 else:
  sum=2
  for no in range(3, n + 1, 2):
   for odd in range(3, int(sqrt(no)) + 1, 2):
    if (no % odd) == 0:
     break
   else:  
    sum+=no
 print(sum)

from math import sqrt
t = int(input())
for _ in range(t):
 n = int(input())
 sum_of_primes = 0
 if n<2:
  pass
 elif n==2:
  sum_of_primes = 2
 else:
  sum_of_primes = 2
  for number in range(3, n + 1, 2):
   for odd in range(3, int(sqrt(number)) + 1, 2):
    if (number % odd) == 0:
     break
   else:  
    sum_of_primes += number
 print(sum_of_primes)

N = (10 ** 6 + 10)
def sieve():
 primes = [0,0] + [1] * N
 sums = 0
 for i in range(2, N):
  if primes[i]:
   for j in range(i*i, N, i):
    primes[j] = 0
 prime_sums = [0] * N
 now = 0
 for i in range(2, N):
  if primes[i]:now += i
  prime_sums[i] = now
 return prime_sums



prime = sieve()
for i in range(int(input())):
 print(prime[int(input())])



# cook your dish here
def sieve(n):
 prime = [True for i in range(n+1)]
 p = 2
 while (p * p <= n):
  if (prime[p] == True):
   for i in range(p * p, n+1, p):
    prime[i] = False
  p += 1
 return prime
for u in range(int(input())):
 n=int(input())
 l=sieve(n)
 s=0
 for i in range(2,n+1):
  if(l[i]==True):
   s=s+i
 print(s)


n=int(input())
x=[]
l=0
for i in range(n):
 m=int(input())
 for g in range(2,m+1):
  for j in range(2,int(g**0.5)+1):
   if g%j==0:
    l=l+1
  if l<=0:        
   x.append(g) 
  l=0 
 print(sum(x))
 x.clear()


try:
 def solver(n):
  prime = [True for i in range(n+1)]
  p = 2
  while(p*p<=n):
   if(prime[p]==True):
    for i in range(p*2,n+1,p):
     prime[i] = False
   p+=1
  prime[0]= False
  prime[1] = False
  s = 0
  for i in range(n+1):
   if(prime[i]):
    s+=i
  return s 
  
 t = int(input())
 for i in range(t):
  n = int(input())
  print(solver(n))
  
 
 
 
except Exception as e:
 pass

# cook your dish here
def primes(n):
 count=0
 prime = [True for i in range(n+1)]
 p = 2
 while (p * p <= n):
  if (prime[p] == True):
   for i in range(p * p, n + 1, p):
    prime[i] = False
  p += 1
 for p in range(2, n + 1):
  if prime[p]:
   count += p
 return count
cases = int(input())
for i in range(cases):
 l = int(input())
 print(primes(l))

def sumOfPrimes(n): 
 prime = [True] * (n + 1) 
 p = 2
 while p * p <= n: 
  if prime[p] == True: 
   i = p * 2
   while i <= n: 
    prime[i] = False
    i += p 
  p += 1 
   
 sum = 0
 for i in range (2, n + 1): 
  if(prime[i]): 
   sum += i 
 return sum
for _ in range(int(input())):
 print(sumOfPrimes(int(input())))

# cook your dish here
try:
 def isprime(n):
  if n==1:
   return False
  if n==2 or n==3:
   return True
  if n%2==0 or n%3==0:
   return False
  j=5
  while(j*j<=n):
   if n%j==0 or n%(j+2)==0:
    return False
   j+=6
  return True
 test=int(input())
 for i in range(test):
  n=int(input())
  s=0
  for j in range(1,n+1):
   if(isprime(j)):
    s+=j
  print(s)
except Exception as e:
 print(e)

def isprime(n):
 if n==2:
  return 1
 for i in range(2,int(n**0.5)+1):
  if n%i==0:
   return 0
 return 1 
t=int(input())
for z in range(t):
 n=int(input())
 s=0
 for i in range(2,n+1):
  if isprime(i):
   s+=i
 print(s) 


def primes(n):
 nums = [True for i in range(n+1)] 
 lst = []
 p = 2
 while (p * p <= n): 
  if (nums[p] == True): 
   for i in range(p * p, n+1, p): 
    nums[i] = False
  p += 1
 for p in range(2, n+1): 
  if nums[p]: 
   lst.append(p)
 return lst
for _ in range(int(input())):
 n = int(input())
 lst = primes(n)
 print(sum(lst))