Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Little Churu is a naughty child, who likes to play with balls. He has N buckets. Each bucket contains one or more balls. He has numbered his buckets 1 to N (both inclusive). He has an infinite supply of extra balls, apart from the ones already in the buckets. He wants to add zero or more number of balls to each of the buckets in such a way, that number of balls in the buckets are in a non-decreasing order, and their GCD is strictly greater than 1.

He wants to do it using the minimum number of extra balls. As he is too young to solve the problem, please help him with the solution.

------ Input ------ 

First line of input contains an integer T denoting the number of test cases.
For each test case, first line contains an integer N denoting the number of buckets.
Second line of each test case contains N space separated integers, where the i^{th} denotes the number of balls in the i^{th} bucket.

------ Output ------ 

For each test case, output a line containing a single integer — the answer for that test case.

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

Subtask #1: 20 points

	$1 ≤ T  ≤ 10, 1 ≤ N  ≤ 1000, 1 ≤ number of balls in a bucket  ≤ 1000$

Subtask #2: 80 points

	$1 ≤ T  ≤ 10, 1 ≤ N  ≤ 10000, 1 ≤ number of balls in a bucket  ≤ 10000$

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

3

11 13 15
----- Sample Output 1 ------ 
3
----- explanation 1 ------ 

Add one ball to each of the buckets.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
prime = [1] * 10003
primes = []

def seive():
	for i in range(2, 10003):
		if prime[i]:
			for j in range(i * i, 10003, i):
				prime[j] = False
			primes.append(i)
t = int(input())
seive()
for testcase in range(t):
	n = int(input())
	v = list(map(int, input().split()))
	count = 0
	for i in range(1, n):
		if v[i] < v[i - 1]:
			count += v[i - 1] - v[i]
			v[i] = v[i - 1]
	ans = 10 ** 9
	for i in primes:
		if i > v[-1]:
			break
		required = 0
		tempans = count
		for j in v:
			if required < j:
				required = (j + i - 1) // i * i
			tempans += required - j
			if tempans > ans:
				break
		if ans > tempans:
			ans = tempans
	print(n) if v[-1] < 2 else print(ans)


from math import gcd as hcf
from functools import reduce
(pf, spf) = ([], [False] * 102)
for i in range(2, 102):
	if spf[i] == False:
		pf.append(i)
		for j in range(i ** 2, 102, i):
			spf[j] = i
for _ in range(int(input())):
	(n, ans) = (int(input()), 0)
	arr = [int(i) for i in input().split()]
	for i in range(1, n):
		if arr[i] < arr[i - 1]:
			ans += arr[i - 1] - arr[i]
			arr[i] += arr[i - 1] - arr[i]
	gcd = reduce(hcf, arr)
	if gcd != 1:
		print(ans)
		continue
	min_ = float('inf')
	for i in pf:
		(ct, minballs) = (0, 0)
		for j in range(n):
			minballs = max((arr[j] + i - 1) // i * i, minballs)
			ct += minballs - arr[j]
		min_ = min(ct, min_)
	print(ans + min_)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	best = float('inf')
	extra = 0
	if arr[0] != 1:
		prev = arr[0]
		for i in range(n):
			if i == 0:
				continue
			if arr[i] < prev:
				extra += prev - arr[i]
			else:
				extra += (arr[0] - arr[i] % arr[0]) % arr[0]
				prev = arr[i] + (arr[0] - arr[i] % arr[0]) % arr[0]
		best = extra
	for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]:
		extra = 0
		prev = arr[0]
		for i in range(n):
			if i == 0:
				extra += (p - arr[i] % p) % p
				prev += (p - arr[i] % p) % p
				continue
			if arr[i] < prev:
				extra += prev - arr[i]
			else:
				extra += (p - arr[i] % p) % p
				prev = arr[i] + (p - arr[i] % p) % p
		best = min(best, extra)
	print(best)


inf = 10 ** 10
sz = 10 ** 4 + 1
stat = [0] * sz
stat[0] = 1
stat[1] = 1
prime = []
for i in range(2, int(sz ** 0.5 + 1)):
	if stat[i] == 0:
		for j in range(i * i, sz, i):
			stat[j] = 1
for i in range(sz):
	if stat[i] == 0:
		prime.append(i)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = len(l) * 2
	t = 0
	for i in range(1, n):
		if l[i] < l[i - 1]:
			t += l[i - 1] - l[i]
			l[i] = l[i - 1]
	m = max(l)
	for i in prime:
		temp = 0
		for j in l:
			if j % i != 0:
				temp += i - j % i
			if temp > ans:
				break
		ans = min(ans, temp)
		if i > m:
			break
	print(ans + t)


from cmath import inf
p = []
primes = [1] * (10 ** 4 + 1)
primes[0] = primes[1] = 0
for i in range(2, 10 ** 4 + 1):
	if primes[i]:
		p.append(i)
		x = 2
		while i * x <= 10 ** 4:
			primes[i * x] = 0
			x += 1
for _ in range(int(input())):
	n = int(input())
	v = list(map(int, input().split()))
	count = 0
	for i in range(1, n):
		if v[i] < v[i - 1]:
			count += v[i - 1] - v[i]
			v[i] = v[i - 1]
	ans = inf
	for i in p:
		if i > v[-1]:
			break
		required = 0
		tempans = count
		for j in v:
			if required < j:
				required = (j + i - 1) // i * i
			tempans += required - j
			if tempans > ans:
				break
		if ans > tempans:
			ans = tempans
	print(n) if v[-1] < 2 else print(ans)


from functools import *
from math import *
from collections import *
prime = []

def isprime(n):
	if n == 2 or n == 3:
		return True
	if n % 2 == 0 or n % 3 == 0 or n <= 1:
		return False
	x = 5
	while x * x <= n:
		if n % x == 0 or n % (x + 2) == 0:
			return False
		x += 6
	return True
for i in range(1, 1002):
	if isprime(i):
		prime.append(i)
for _ in range(int(input().strip())):
	n = int(input().strip())
	l = list(map(int, input().strip().split()))
	ans1 = 0
	for i in range(1, n):
		if l[i] < l[i - 1]:
			ans1 += l[i - 1] - l[i]
			l[i] += l[i - 1] - l[i]
	gc = reduce(gcd, l)
	if gc != 1:
		print(ans1)
		continue
	else:
		ans = 10 ** 6
		for i in range(len(prime)):
			x = 0
			for j in range(n):
				y = l[j] % prime[i]
				if y != 0:
					x += prime[i] - y
			ans = min(ans, x)
		print(ans + ans1)


def test():
	n = int(input())
	a = [int(i) for i in input().split(' ')]
	for_sure = 0
	for i in range(1, len(a)):
		if a[i] < a[i - 1]:
			for_sure += a[i - 1] - a[i]
			a[i] = a[i - 1]
	maybe = sum((i % 2 for i in a))
	ln = a[0] + maybe
	prost = [1 for i in range(ln + 1)]
	prost[0] = 0
	prost[1] = 0
	for i in range(2, int(ln ** 0.5) + 1):
		if prost[i]:
			for j in range(2 * i, ln + 1, i):
				prost[j] = 0
	prost = [i for i in range(3, ln + 1) if prost[i]]
	for i in prost:
		try_maybe = 0
		for j in a:
			try_maybe += 0 if j % i == 0 else i - j % i
			if try_maybe >= maybe:
				break
		else:
			maybe = try_maybe
	return for_sure + maybe

def main():
	T = int(input())
	for i in range(T):
		print(test())
main()