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

Input:
1
3
11 13 15

Output:
3


Explanation

Add one ball to each of the buckets.
T = int(raw_input())
n = []
a = []
m = []

for t in xrange(T):
	n.append(int(raw_input()))
	a.append(map(int, raw_input().split()))
	m.append(max(a[-1]))

M = max(m)
l = [False, False] + [True] * (M-1)

for i in xrange(2,M+1):
	if (l[i]):
		for j in range(2*i, M+1, i):
			l[j]=False

for t in xrange(T):
	x = 0
	for i in xrange(1, n[t]):
		if (a[t][i] < a[t][i-1]):
			x += a[t][i-1] - a[t][i]
			a[t][i] = a[t][i-1]
	y = 0
	for j in a[t]:
		y += ((2 - (j % 2)) % 2)
	for i in range(3,m[t]+1):
		temp = 0
		if (l[i]):
			for j in a[t]:
				temp += ((i - (j % i)) % i)
				if (temp > y):
					break
			y = min(y,temp)
			if (y == 0):
				break
	print x+y