Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Zanka finds fun in everyday simple things. One fine day he got interested in a very trivial sequence. Given a natural number $k$, he considers the sequence $A_{i}=k+i^{2}$ so that the terms are

$$k+1,k+4,k+9,k+16, \ldots $$
	
Now to make things more interesting, he considers the $\gcd$ of consecutive terms in the sequence, then takes the sum of the first $2k$ values. More formally, he wants to compute

$$\sum_{i=1}^{2k} \gcd(A_{i},A_{i+1})$$

Denote this sum by $S$. Zanka wants you to print  the number $S$ for each $k$.

------ Input ------
The first line contains an integer $T$, the number of test cases. Descriptions of test cases follow.
The only line of each test case contains a single integer $k$.

------ Output ------
For each test case, output a single line containing the sum $S$ for the given $k$.

------ Constraints ------
$1 ≤ T ≤ 10^{6}$
$1 ≤ k ≤ 10^{6}$

------ Subtasks ------
Subtask #1 (20 points): $t ≤ 10^{3}$,$k ≤ 10^{3}$

Subtask #2 (80 points): Original Constraints

----- Sample Input 1 ------ 
1

1
----- Sample Output 1 ------ 
6
----- explanation 1 ------ 
The first $2k+1$ terms of the sequence $A$ are $2, 5, 10$.

So the answer is $\gcd(2,5) + \gcd(5,10) = 1+5=6$

Source: codechef | Difficulty: HARD
Tags: Number theory

Mathematics


Solutions:
n = 4000001
s = [i for i in range(n + 1)]

def test():
	p = 2
	while p * p <= n:
		if s[p] == p:
			for i in range(p * p, n + 1, p):
				if s[i] >= p:
					s[i] = p
		p += 1
test()

def f(x):
	d = dict()
	while x != 1:
		t = s[x]
		if t in d:
			d[t] += 1
		else:
			d[t] = 1
		x = x // t
	return d

def A(k):
	ans = 1
	d = f(4 * k + 1)
	for i in d:
		ans *= d[i] + 1 - d[i] / i
	return round(4 * k + (ans - 1) / 2 * (4 * k + 1))
L = [1]
for i in range(1, 10 ** 6 + 1):
	L.append(A(i))
T = int(input())
for n1 in range(T):
	k = int(input())
	print(L[k])


def readInt():
	return int(input())

def readInts():
	return [int(x) for x in input().split()]

def readString():
	return input().rstrip()

def readStrings():
	return input().split()
num_cases = readInt()
cases = [readInt() for _ in range(num_cases)]
limit = max(cases)

def factor_table(limit):
	table = list(range(limit + 1))
	for n in range(2, limit + 1):
		if table[n] == n:
			for m in range(n * n, limit + 1, n):
				table[m] = min(table[m], n)
	return table
table = factor_table(4 * limit + 1)

def factors(n):
	result = []
	while n != 1:
		factor = table[n]
		result.append(factor)
		n //= factor
	return result

def solve(k):
	k = 4 * k + 1
	facts = factors(k)
	(count, current) = (1, facts[0])
	result = 1
	for f in facts[1:]:
		if f != current:
			result *= (count + 1) * current ** count - count * current ** (count - 1)
			(current, count) = (f, 1)
		else:
			count += 1
	result *= (count + 1) * current ** count - count * current ** (count - 1)
	tail = result - k
	return result - (tail // 2 + 1)
for case in cases:
	print(solve(case))