While doing his research in the Institute of Lovely Graphs, Rashad came up with another problem called Prime Graph.

Prime Graph is a simple graph (undirected graph which does not contain any self-loops or multiple-edges) with N nodes such that the degree of each node is prime. Rashad wants to know what is the maximum number of edges a prime graph with N nodes can contain. Can you help Rashad answer this question?

Note: The degree of a node in a simple graph is the number of edges that are incident on the node and a prime number is a natural number greater than 1 which has exactly two divisors - 1 and the number itself.

------ Input Format ------ 

- The first line contains T - the number of test cases. Then the test cases follow.
- The first line of each test case contains N - the number of nodes in the graph. 

------ Output Format ------ 

For each test case, output the maximum number of edges a prime graph of N nodes can contain.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$3 ≤ N ≤ 10^{5}$

----- Sample Input 1 ------ 
3
3
4
5
----- Sample Output 1 ------ 
3
6
7

----- explanation 1 ------ 
- For $N = 3$ and $4$ we can construct a complete graph (a graph in which every pair of distinct vertices is connected by an edge). 
- For $N = 5$ we can construct a prime graph with at most $7$ edges. One such graph is:

Difficulty: VERY_HARD
Tags: Graph algorithms

Starter code:

Solutions:
def SoE(n):
	a = []
	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]:
			a.append(p)
	return (prime, a)

def binary_search(l, r, a, tar):
	if l > r:
		return -1
	m = (l + r) // 2
	if a[m] == tar:
		return m
	elif a[m] < tar:
		return binary_search(m + 1, r, a, tar)
	else:
		return binary_search(l, m - 1, a, tar)
t = int(input())
(a, b) = SoE(100000)
for _ in range(t):
	n = int(input())
	i = n - 1
	while a[i] == False:
		i -= 1
	p = i
	left = n
	curr = binary_search(0, len(b) - 1, b, p)
	value = n * p
	ans = 0
	while left > 0:
		num = value // b[curr]
		if b[curr] == 2:
			pass
		elif num % 2 == 1:
			num = num - 1
		if left - num >= 0:
			left -= num
			ans = num * b[curr]
			curr = curr - 1
		elif b[curr] == 2:
			ans = ans + b[curr] * left
			left = 0
		elif left % 2 == 1:
			ans = ans + b[curr] * (left - 1)
			left = 1
			curr = curr - 1
		else:
			ans = ans + b[curr] * left
			left = 0
			curr = curr - 1
	print(ans // 2)


import sys

def input():
	return sys.stdin.readline().rstrip('\r\n')

def isprime(x):
	y = 1
	i = 3
	while i <= x ** 0.5:
		if x % i == 0:
			y = 0
			break
		i += 2
	return y
for _ in range(int(input())):
	n = int(input())
	if n == 3:
		print(3)
		continue
	tmp = n - 1 if n % 2 == 0 else n - 2
	while not isprime(tmp):
		tmp -= 2
	if n * tmp % 2 == 0:
		print(n * tmp // 2)
	else:
		print(((n - 1) * tmp + 2) // 2)


p = [1] * 100005
p[0] = 0
p[1] = 0
for i in range(2, int(100005 ** 0.5) + 1):
	if p[i]:
		for j in range(i + i, 100005, i):
			p[j] = 0
t = int(input())
for _ in range(t):
	n = int(input())
	for i in range(100005):
		if i < n:
			if p[i]:
				lp = i
		else:
			break
	t = n * lp
	if t % 2:
		print(((n - 1) * lp + 2) // 2)
	else:
		print(t // 2)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def sieve():
	prime = [True] * (10 ** 5 + 1)
	(prime[0], prime[1]) = (False, False)
	for i in range(2, int(math.sqrt(10 ** 5 + 1)) + 1):
		if prime[i] == True:
			for j in range(i * i, 10 ** 5 + 1, i):
				prime[j] = False
	return prime
d = sieve()
res = []
for i in range(10 ** 5 + 1):
	if d[i]:
		res.append(i)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		n = inpu()
		idx = bisect.bisect_left(res, n) - 1
		val = res[idx] - 2
		if n & 1:
			print(n + (n - 1) // 2 * val)
		else:
			print(n + n // 2 * val)
main()


def snek(x):
	for j in range(2, x):
		if x % j == 0:
			return False
	return True
t = int(input())
for i in range(t):
	n = int(input())
	c = 0
	for j in range(n - 1, 1, -1):
		if snek(j):
			c = j
			break
	if n % 2 == 0:
		ans = n * c // 2
	else:
		ans = ((n - 1) * c + 2) // 2
	print(ans)


def prime(a):
	for i in range(2, a):
		if a % i == 0:
			return False
	return True
for i in range(int(input())):
	n = int(input())
	p = 0
	for i in range(n - 1, 1, -1):
		if prime(i):
			p = i
			break
	if n % 2 == 0:
		ans = n * p // 2
	else:
		ans = ((n - 1) * p + 2) // 2
	print(ans)


n = 10 ** 6

def SieveOfEratosthenes(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
prime = SieveOfEratosthenes(n)
t = int(input())
for i in range(t):
	nodes = int(input())
	l_prime = nodes - 1
	while not prime[l_prime]:
		l_prime -= 1
	if nodes % 2 == 0:
		deg_sum = l_prime * nodes
	else:
		deg_sum = l_prime * (nodes - 1) + 2
	print(deg_sum // 2)


def SieveOfEratosthenes(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
	primes = []
	for p in range(n + 1):
		if prime[p]:
			primes.append(p)
	return primes

def lowerBound(ls, key):
	lowerInd = 0
	while lowerInd < len(ls):
		if key > ls[lowerInd]:
			lowerInd += 1
		else:
			return lowerInd
	return lowerInd
t = int(input())
primes = SieveOfEratosthenes(10 ** 6 + 1)
for _ in range(t):
	n = int(input())
	ind = lowerBound(primes, n)
	if primes[ind] > n - 1:
		ind -= 1
	max = n * primes[ind]
	if max % 2 == 1:
		max = primes[ind] * (n - 1) + 2
	print(max // 2)


def ss(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
	for p in range(n, 1, -1):
		if prime[p]:
			return p
for _ in range(int(input())):
	n = int(input())
	if not n % 2:
		print(ss(n - 1) * n // 2)
	else:
		print(ss(n - 1) * (n - 1) // 2 + 1)


def SieveOfEratosthenes(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
	for p in range(2, n + 1):
		if prime[p]:
			f.append(p)

def bs(val, n):
	(l, r) = (0, n - 1)
	ans = 0
	while l <= r:
		mid = l + (r - l) // 2
		c = f[mid]
		if c == val:
			return val
		elif c > val:
			r = mid - 1
		else:
			ans = max(ans, f[mid])
			l = mid + 1
	return ans
f = []
SieveOfEratosthenes(10 ** 5 + 10)
l = len(f)
for i in range(int(input())):
	n = int(input())
	v = bs(n - 1, l)
	if n & 1:
		ans = (n - 1) * v // 2
		ans += 1
	else:
		ans = n * v // 2
	print(ans)


prime_table = []

def sieve(limit):
	global prime_table
	prime_table = [False, False, True] + [True, False] * (limit // 2 + 1)
	for i in range(3, int(limit ** 0.5) + 1, 2):
		if prime_table[i]:
			for j in range(i * i, limit + 1, i * 2):
				prime_table[j] = False

def isPrime(num):
	global prime_table
	return prime_table[num]
sieve(pow(10, 6))
for _ in range(int(input())):
	n = int(input())
	largest_prime = n - 1
	while not isPrime(largest_prime):
		largest_prime -= 1
	total = n * largest_prime
	if total % 2 == 1:
		total = (n - 1) * largest_prime + 2
	print(total // 2)


from bisect import bisect, bisect_left
from math import ceil

def seive_of_eratosthenes(n):
	is_prime = [True for _ in range(n + 1)]
	(is_prime[0], is_prime[1]) = (False, False)
	for i in range(2, int(n ** 0.5) + 1):
		for j in range(2 * i, n + 1, i):
			is_prime[j] = False
	res = []
	for i in range(2, n):
		if is_prime[i]:
			res.append(i)
	return res
p = seive_of_eratosthenes(10 ** 5 + 10)
for _ in range(int(input())):
	n = int(input())
	a = bisect_left(p, n - 1)
	if p[a] != n - 1:
		a -= 1
	v = p[a]
	if n % 2 == 0:
		print(n // 2 * v)
	else:
		print((n - 1) // 2 * v + 1)


import math

def fun(n):
	if n == 2:
		return False
	a = int(math.sqrt(n))
	for i in range(2, a + 2):
		if n % i == 0:
			return True
	return False
for _ in range(int(input())):
	n = int(input())
	e = n - 1
	while fun(e):
		e -= 1
	if n & 1 == 0:
		print(n * e // 2)
	else:
		print((n - 1) * e // 2 + 1)


from math import sqrt

def isPrime(n):
	if n <= 1:
		return False
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

def getprime(n):
	if isPrime(n):
		return n
	return getprime(n - 1)
for _ in range(int(input())):
	n = int(input())
	val = getprime(n - 1)
	ans = n * val
	if ans % 2 != 0:
		ans = (n - 1) * val + 2
	print(ans // 2)


from sys import stdin
input = stdin.readline
size = 2 * 10 ** 5 + 1
isprime = [True] * size
isprime[0] = False
isprime[1] = False
prime = []
for i in range(2, size):
	if isprime[i]:
		for j in range(i + i, size, i):
			isprime[j] = False
		prime.append(i)

def answer():
	for i in range(len(prime)):
		if prime[i] > n - 1:
			p = prime[i - 1]
			break
	if n & 1 == 0:
		ans = n * p // 2
	else:
		ans = (n - 1) * p // 2 + 1
	return ans
for T in range(int(input())):
	n = int(input())
	print(answer())


from bisect import bisect_left as bl
a = []

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			a.append(p)
sieve(10 ** 5)
for _ in range(int(input())):
	n = int(input())
	t = bl(a, n - 1)
	if t >= len(a) or a[t] > n - 1:
		t -= 1
	deg = a[t]
	if n % 2:
		print((deg * (n - 1) + 2) // 2)
	else:
		print(deg * n // 2)


import bisect
prime = [1] * (10 ** 5 + 5)
prime[0] = 0
prime[1] = 0

def sieve():
	max_n = 10 ** 5
	i = 2
	while i * i <= max_n:
		if prime[i]:
			for j in range(i * i, max_n + 1, i):
				prime[j] = 0
		i += 1
sieve()
prime = [i for i in range(len(prime)) if prime[i] == 1]
t = int(input())
for i in range(t):
	n = int(input())
	if n == 3:
		print(3)
	elif n == 4:
		print(6)
	elif n == 5:
		print(7)
	else:
		idx = bisect.bisect_left(prime, n) - 1
		val = prime[idx] - 2
		if n & 1:
			print(n + (n - 1) // 2 * val)
		else:
			print(n + n // 2 * val)


array_of_primes = []
for i in range(2, 10 ** 5 + 5000):
	yesval = 'no'
	for j in range(2, min(round(i ** 0.5) + 2, i)):
		if i % j == 0:
			yesval = 'yes'
			break
	if yesval == 'no':
		array_of_primes.append(i)
T = int(input())
for i in range(T):
	N = int(input())
	val = 2
	if N == 3:
		print(3)
	elif N % 2 == 0:
		for theta in range(10 ** 4):
			if array_of_primes[theta] >= N:
				val = array_of_primes[theta - 1]
				break
		print(val * N // 2)
	else:
		for theta in range(10 ** 4):
			if array_of_primes[theta] >= N:
				val = array_of_primes[theta - 1]
				break
		print(val * (N - 1) // 2 + 1)


from bisect import bisect_left

def prime_list(n):
	primes = []
	arr = [True] * n
	for i in range(2, n):
		if arr[i]:
			primes.append(i)
			j = i
			while j <= n - 1:
				arr[j] = False
				j += i
	return primes

def largest_prime(n):
	x = bisect_left(primes, n)
	return primes[x - 1]

def solve(n):
	p = largest_prime(n)
	if n % 2 == 0:
		return n * p // 2
	else:
		return ((n - 1) * p + 2) // 2
primes = prime_list(100000)
T = int(input())
for _ in range(T):
	n = int(input())
	result = solve(n)
	print(result)


import sys, os, io
input = sys.stdin.readline
from collections import defaultdict
import bisect
import random
PI = 3.141592653589793
INF = float('inf')
MOD = 1000000007

def bin32(num):
	return '{0:032b}'.format(num)

def add(x, y):
	return (x + y) % MOD

def sub(x, y):
	return (x - y + MOD) % MOD

def mul(x, y):
	return x * y % MOD

def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)

def lcm(x, y):
	return x * y // gcd(x, y)

def power(x, y):
	res = 1
	x %= MOD
	while y != 0:
		if y & 1:
			res = mul(res, x)
		y >>= 1
		x = mul(x, x)
	return res

def mod_inv(n):
	return power(n, MOD - 2)

def prob(p, q):
	return mul(p, power(q, MOD - 2))

def ii():
	return int(input())

def li():
	return [int(i) for i in input().split()]

def ls():
	return [i for i in input().split()]
N = 10 ** 5 + 10
prime = [1 for i in range(N)]
for i in range(2, N):
	if prime[i]:
		for j in range(i + i, N, i):
			prime[j] = 0
p = 2
prev = [0 for i in range(N)]
for i in range(3, N):
	prev[i] = p
	if prime[i]:
		p = i
for t in range(ii()):
	t += 1
	n = ii()
	if n % 2 == 0:
		print(n // 2 * prev[n])
	else:
		print((2 + (n - 1) * prev[n]) // 2)


def largest_prime(n):
	primes = []
	arr = [True] * n
	for i in range(2, n):
		if arr[i]:
			primes.append(i)
			j = i
			while j <= n - 1:
				arr[j] = False
				j += i
	return primes[-1]

def solve(n):
	p = largest_prime(n)
	if n % 2 == 0:
		return n * p // 2
	else:
		return ((n - 1) * p + 2) // 2
T = int(input())
for _ in range(T):
	n = int(input())
	result = solve(n)
	print(result)


import sys
import math
import random
import heapq
input = sys.stdin.readline

def pow(a, n, m):
	if n == 0:
		return 1
	x = pow(a, n // 2, m)
	if n % 2 == 0:
		return x * x % m
	else:
		return x * x * a % m

def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a

def bs(arr, le, ri):
	l = 0
	arr.sort()
	r = len(arr) - 1
	ans = 10000000
	while l <= r:
		m = (l + r) // 2
		if arr[m] >= le and arr[m] <= ri:
			ans = arr[m]
			r = m - 1
		elif arr[m] < le:
			l = m + 1
		else:
			r = m - 1
	return ans

def dfs(al, l, p, n, le, pa):
	l[n] = le
	p[n] = pa
	for i in al[n]:
		if i != pa:
			dfs(al, l, p, i, le + 1, n)

def lca(al, l, p, x, y):
	if l[x] > l[y]:
		(x, y) = (y, x)
	d = l[y] - l[x]
	while d != 0:
		y = p[y]
		d -= 1
	while x != y:
		x = p[x]
		y = p[y]
	return x

def dfs1(al, i, x, y, vis, p, ans):
	vis[i] = 1
	if i == x or i == y:
		p = 1
	ans[i] = p
	for j in al[i]:
		if vis[j] == 0:
			dfs1(al, j, x, y, vis, p, ans)
l = [1] * 100001
l[0] = 0
l[1] = 0
for i in range(2, 1001):
	if l[i] == 1:
		j = i
		while j * i <= 100000:
			l[j * i] = 0
			j += 1
ls = [2] * 100001
p = 3
for i in range(4, 100001):
	ls[i] = p
	if l[i] == 1:
		p = i
t = 1
t = int(input())
while t > 0:
	n = int(input())
	if n * ls[n] % 2 == 0:
		print(n * ls[n] // 2)
	else:
		print((n - 1) * ls[n] // 2 + 1)
	t -= 1


from bisect import *
t = int(input())
primes = []
vis = [0] * (10 ** 5 + 5)
for i in range(2, 10 ** 5 + 1):
	if vis[i] == 0:
		primes.append(i)
		for j in range(i, 10 ** 5 + 1, i):
			vis[j] = 1
for _ in range(t):
	t -= 1
	n = int(input())
	z = bisect_right(primes, n - 1)
	z -= 1
	if n % 2 == 0:
		ed = n * primes[z]
		ed = ed // 2
	else:
		ed = (n - 1) * primes[z]
		ed += 2
		ed = ed // 2
	print(ed)