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

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


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)


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 ** 0.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)


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())])


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


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())))


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))