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

For a set of positive integers $S$, let's define $\mathrm{gcd}(S)$ as the greatest integer which divides each element of $S$. If $\mathrm{gcd}(S) = 1$, the set $S$ is called *coprime*. For example, the set $\{7, 12, 15\}$ is coprime, but $\{6, 12, 15\}$ is not coprime, since every element of this set is divisible by $3$.

Your task is to find an integer sequence $A_{0}, A_{1}, \ldots, A_{N-1}$ such that:
for each valid $i$, $1 ≤ A_{i} ≤ 10^{9}$
$A_{0}, A_{1}, \ldots, A_{N-1}$ are pairwise distinct
for each valid $i$, the set $\{A_{i}, A_{(i+1)\%N}\}$ is not coprime ($\%$ denotes the modulo operator)
for each valid $i$, the set $\{A_{i}, A_{(i+1)\%N}, A_{(i+2)\%N}\}$ is coprime

It is possible that there is no solution. If there are multiple solutions, you may find any one.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains a single integer $N$.

------  Output ------
For each test case:
If there is no solution, print a single line containing the integer $-1$.
Otherwise, print a single line containing $N$ space-separated integers $A_{0}, A_{1}, \ldots, A_{N-1}$.

------  Constraints ------
$1 ≤ T ≤ 1,000$
$3 ≤ N ≤ 50,000$
the sum of $N$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (19 points): $3 ≤ N ≤ 3,333$

Subtask #2 (81 points): original constraints

----- Sample Input 1 ------ 
2
3
4
----- Sample Output 1 ------ 
6 10 15
374 595 1365 858
----- explanation 1 ------ 
Example case 1: Let's check the answer: $\mathrm{gcd}(6, 10) = 2$, $\mathrm{gcd}(10, 15) = 5$, $\mathrm{gcd}(15, 6) = 3$, $\mathrm{gcd}(6, 10, 15) = 1$. Every two cyclically consecutive numbers are not coprime, but every three cyclically consecutive numbers are coprime.

Example case 2:
- $\mathrm{gcd}(374, 595) = 17$, $\mathrm{gcd}(595, 1365) = 35$, $\mathrm{gcd}(1365, 868) = 39$, $\mathrm{gcd}(858, 374) = 22$
- $\mathrm{gcd}(374, 595, 1365) = 1$, $\mathrm{gcd}(595, 1365, 858) = 1$, $\mathrm{gcd}(1365, 858, 374) = 1$, $\mathrm{gcd}(858, 374, 595) = 1$

Difficulty: HARD
Tags: Number theory

Mathematics

Constructive algorithms

Starter code:

Solutions:
a = []
for i in range(7, 62600):
	if i % 2 != 0 and i % 3 != 0 and (i % 5 != 0):
		a.append(i)
t = int(input())
for i in range(t):
	n = int(input())
	if n % 3 == 0:
		m = []
		for i in range((n - 3) // 3):
			if i % 2 == 0:
				x = 6 * a[i]
				y = 10 * a[i + 1]
				z = 15 * a[i]
				m.append(x)
				m.append(y)
				m.append(z)
			else:
				x = 6 * a[i]
				y = 10 * a[i - 1]
				z = 15 * a[i]
				m.append(x)
				m.append(y)
				m.append(z)
		m = [6, 10, 15] + m
		print(*m)
	if n % 3 == 1:
		m = []
		for i in range((n - 4) // 3):
			if i % 2 == 0:
				x = 6 * a[i]
				y = 10 * a[i + 1]
				z = 15 * a[i]
				m.append(x)
				m.append(y)
				m.append(z)
			else:
				x = 6 * a[i]
				y = 10 * a[i - 1]
				z = 15 * a[i]
				m.append(x)
				m.append(y)
				m.append(z)
		m = [6, 10, 15] + m
		m = m[6:]
		if n == 4:
			print(374, 595, 1365, 858)
		else:
			m = [6, 10, 15, 21, 77, 110, 105] + m
			print(*m)
	if n % 3 == 2:
		m = []
		for i in range((n - 5) // 3):
			if i % 2 == 0:
				x = 6 * a[i]
				y = 10 * a[i + 1]
				z = 15 * a[i]
				m.append(x)
				m.append(y)
				m.append(z)
			else:
				x = 6 * a[i]
				y = 10 * a[i - 1]
				z = 15 * a[i]
				m.append(x)
				m.append(y)
				m.append(z)
		m = [6, 10, 15] + m
		m = m[6:]
		if n == 5:
			print(6, 15, 35, 77, 22)
		else:
			m = [6, 10, 15, 33, 77, 14, 110, 105] + m
			print(*m)


import sys
import math

def inputIntTuple():
	return tuple([int(x) for x in sys.stdin.readline().strip().split()])

def inputIntList():
	return [int(x) for x in sys.stdin.readline().strip().split()]

def getInt():
	return int(sys.stdin.readline().strip())

def firstNonZero(list, start):
	for i in range(start, len(list)):
		if list[i]:
			return (i, list[i])
	return (None, None)

def collectPrimes(sieve, include2):
	ps = []
	if include2:
		ps.append(2)
	for p in sieve:
		if p:
			ps.append(p)
	return ps

def sieve(start, end):
	s = [0 if (x + start) % 2 == 0 or x + start == 1 else x + start for x in range(end - start + 1)]
	inc = 3
	maxInc = max((end - start) // 2, math.ceil(math.sqrt(end)))
	while inc <= maxInc:
		(idx, firstNonZeroValue) = firstNonZero(s, 0)
		if not firstNonZeroValue:
			break
		startIdx = idx
		if s[idx] % inc != 0:
			startIdx = idx + inc - s[idx] % inc
		if startIdx < len(s) and s[startIdx] // inc > 1:
			s[startIdx] = 0
		for next in range(startIdx + inc, len(s), inc):
			s[next] = 0
		inc += 2
	return collectPrimes(s, start <= 2)

def testSet(S):
	N = len(S)
	uni = set()
	uni.update(S)
	if N != len(uni):
		print('Have duplicates - %d' % (len(uni) - N))
	for i in range(N):
		a = S[i]
		if a > 1000000000:
			print('Too big')
			return False
		b = S[(i + 1) % N]
		c = S[(i + 2) % N]
		if gcd(a, b) == 1:
			print('not divisible at idx:%d ( %d %d )' % (i, a, b))
			return False
		if gcd(b, c) == 1:
			print('not divisible at idx:%d ( %d %d )' % (i, b, c))
			return False
		if not coprime(a, b, c):
			print('idx: %d; %d %d %d' % (i, a, b, c))
			print(gcd(a, c))
			return False
	return True

def bulkTest(ps):
	for N in range(3000, 50000):
		S = gen(N, ps)
		if not testSet(S):
			print('%d FAILED' % N)
	print('done')

def genLE3333(N, ps):
	seq = [1] * N
	P = len(ps)
	primeDistIdx = 251
	dist = ps[primeDistIdx]
	idx = 0
	generated = 0
	pidx = 0
	lastInSeq = 0
	while generated < N:
		if generated % 3300 == 0:
			primeDistIdx += 1
			dist = ps[primeDistIdx]
		pidx %= P
		nextPrimeIdx = pidx + dist
		if nextPrimeIdx >= P:
			nextPrimeIdx %= P
		if nextPrimeIdx == 0:
			primeDistIdx += 1
			nextPrimeIdx = ps[primeDistIdx]
		next = ps[pidx] * ps[nextPrimeIdx]
		seq[idx] = next
		lastInSeq = seq[idx]
		generated += 1
		idx += 1
		pidx += dist
	seq[N - 1] *= 2
	return seq

def genGT3333(N, ps):
	seq = [1] * N
	P = len(ps)
	primeDistIdx = 251
	dist = ps[primeDistIdx]
	idx = 0
	generated = 0
	pidx = 0
	lastInSeq = 0
	while generated < N:
		if generated % 2500 == 0:
			primeDistIdx += 1
			dist = ps[primeDistIdx]
		pidx %= P
		nextPrimeIdx = pidx + dist
		if nextPrimeIdx >= P:
			nextPrimeIdx %= P
		next = ps[pidx] * ps[nextPrimeIdx]
		seq[idx] = next
		lastInSeq = seq[idx]
		generated += 1
		idx += 1
		pidx += dist
	seq[N - 1] *= 2
	return seq

def concat(cops, N):
	return ' '.join([str(x) for x in cops[:N]])

def format(S):
	return ' '.join([str(x) for x in S])

def gcd(a, b):
	assert a >= 0 and b >= 0 and (a + b > 0)
	while a > 0 and b > 0:
		if a >= b:
			a %= b
		else:
			b %= a
	return max(a, b)

def coprime(a, b, c):
	return gcd(gcd(a, b), c) == 1

def main():
	ps = sieve(1, 30940)
	if len(ps) % 2 == 0:
		ps.pop()
	T = getInt()
	while T > 0:
		T -= 1
		N = getInt()
		if N == 3:
			print('6 10 15')
			continue
		if N == 4:
			print('374 595 1365 858')
			continue
		S = genGT3333(N, ps)
		if N <= 3333:
			S = genLE3333(N, ps)
		print(format(S))
main()


def primes(n):
	a = []
	prime = [1] * (n + 1)
	imp = 0
	imp = imp + 2
	while imp ** 2 <= n:
		if prime[imp] == 1:
			for i in range(imp ** 2, n + 1, imp):
				prime[i] = 0
		imp += 1
	imp = 2
	while imp <= n - 1:
		if prime[imp] == 1:
			a.append(imp)
		imp = imp + 1
	return a
a = primes(650000)
d = a[:]
g = a
c = [1]
a = c + a
b = int(input())
for i in range(b):
	c = int(input())
	if c <= 3333:
		if c == 3:
			print(6, 10, 15)
		elif c == 4:
			print(374, 595, 1365, 858)
		elif c >= 4:
			print(g[0] * g[c - 1], end=' ')
			for i in range(1, c):
				print(g[i] * a[i], end=' ')
			print()
	else:
		a = d[:]
		a[0] = a[0] * 11
		for i in range(1, c - 1):
			if i % 3 == 1:
				a[i] = a[i] * 6
			elif i % 3 == 0:
				a[i] = a[i] * 10
			elif i % 3 == 2:
				a[i] = a[i] * 15
		a[c - 2] = a[c - 2] * 23
		a[c - 1] = a[c - 1] * 253
		for i in range(c):
			print(a[i], end=' ')
		print()


prime_num = []

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 * 2, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n):
		if prime[p]:
			prime_num.append(p)
Sieve(330000)
__ = [[15, 6, 10], [595, 1365, 858, 374], [55, 77, 21, 6, 10], [10, 65, 143, 77, 21, 6]]
___ = [[18, 45, 10, 14, 63, 99, 22], [18, 45, 35, 14, 22, 99, 117, 26], [18, 45, 35, 77, 22, 26, 117, 153, 34], [18, 45, 35, 77, 143, 26, 34, 153, 171, 38]]
index = [5, 6, 7, 8]
m = [2, 3, 9, 2]
for _ in range(int(input())):
	n = int(input())
	if n < 7:
		print(*__[n - 3])
	elif n < 11:
		print(*___[n - 7])
	else:
		numbers_remain_to_print = n - 7
		reminder = numbers_remain_to_print % 4
		prime_ptr = index[reminder]
		print(*___[reminder], end=' ')
		numbers_remain_to_print = n - len(___[reminder])
		while numbers_remain_to_print > 0:
			count_to = 2
			for prime_number in m:
				print(prime_number * prime_num[prime_ptr], end=' ')
				numbers_remain_to_print -= 1
				if numbers_remain_to_print == 0:
					break
				count_to -= 1
				if count_to == 0:
					prime_ptr += 1
					count_to = 2
		print()