Vasya has ordered a pizza delivery. The pizza can be considered a perfect circle. There were $n$ premade cuts in the pizza when it was delivered. Each cut is a straight segment connecting the center of the pizza with its boundary.
Let $O$ be the center of the pizza, $P_i$ be the endpoint of the $i$-th cut lying on the boundary, and $R$ be the point of the boundary straight to the right of $O$. Then the counterclockwise-measured angle $\angle ROP_i$ is equal to $a_i$ degrees, where $a_i$ is an integer between $0$ and $359$. Note that angles between $0$ and $180$ angles correspond to $P_i$ in the top half of the pizza, while angles between $180$ and $360$ angles correspond to the bottom half.
Vasya may cut his pizza a few more times, and the new cuts still have to be straight segments starting at the center. He wants to make the pizza separated into several equal slices, with each slice being a circular sector with no cuts inside of it. How many new cuts Vasya will have to make?

-----Input:-----
The first line of input contains $T$ , i.e number of test cases per file.
The first line of each test case contains a single integer $n-$  the numbers of premade cuts ($2 \leq n \leq 360$).
The second lines contains $n$ integers $a_1, \ldots, a_n-$ angles of the cuts $1, \ldots, n$ respectively ($0 \leq a_1 < \ldots, a_{n - 1} < 360$).

-----Output:-----
Print a single integer$-$ the smallest number of additional cuts Vasya has to make so that the pizza is divided into several equal slices.

-----Constraints-----
- $1  \leq T  \leq 36$
- $2 \leq n \leq 360$
- $0 \leq a_1 < \ldots, a_{n - 1} < 360$

-----Sample Input:-----
3
4 
0 90 180 270
2
90 210
2
0 1

-----Sample Output:-----
0
1
358

-----EXPLANATION:-----
In the first sample the pizza is already cut into four equal slices.
In the second sample the pizza will be cut into three equal slices after making one extra cut at $330$ degrees.
In the third sample Vasya will have to cut his pizza into $360$ pieces of $1$ degree angle each.

Source: codechef | Difficulty: MEDIUM
Tags: Geometry

Number theory

Mathematics


Solutions:
from functools import reduce
from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	arr = []
	val = 0
	for i in a:
		arr.append(i - val)
		val = i
	arr[0] = 360 - (val - arr[0])
	arr.append(360)
	q = reduce(gcd, arr)
	needed = 360 / q
	print(int(needed - n))


import math
from functools import reduce
for t in range(int(input())):
	n = int(input())
	A = list(map(int, input().split(' ')))
	sizes = []
	for i in range(1, len(A)):
		sizes.append(A[i] - A[i - 1])
	sizes.append(A[0] + 360 - A[-1])
	gd = reduce(lambda x, y: math.gcd(x, y), sizes)
	ans = 0
	for s in sizes:
		ans += s // gd - 1
	print(ans)


from math import gcd
T = int(input())
x = []
for i in range(T):
	n = int(input())
	a = [int(i) for i in input().split()]
	g = a[1] - a[0]
	for i in range(1, n):
		g = gcd(g, a[i] - a[i - 1])
	g = gcd(g, 360 - a[n - 1] + a[0])
	count = 0
	for i in range(1, n):
		count += (a[i] - a[i - 1]) // g - 1
	count += (360 - a[n - 1] + a[0]) // g - 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = []
	if n == 1:
		print(1)
		continue
	ans = []
	for i in range(2, 361):
		c = 0
		temp = 360 // i
		if temp == 360 / i:
			for j in range(1, n):
				if (a[j] - a[j - 1]) % temp == 0:
					c += 1
			if c == n - 1:
				ans.append(i - n)
	print(min(ans))


from math import gcd
from functools import reduce
for _ in range(int(input())):
	N = int(input())
	A = [int(s) for s in input().split()]
	g = reduce(gcd, [(a - b) % 360 for (a, b) in zip(A, A[1:] + [A[0]])], 360)
	print(360 // g - N)


from math import gcd

def fun(n):
	a = list(map(int, input().split()))
	a = a + [a[0]]
	ps = []
	for i in range(n - 1):
		ps.append(a[i + 1] - a[i])
	ps.append(360 + a[0] - a[n - 1])
	gd = ps[n - 1]
	for j in range(n - 1):
		gd = gcd(gd, ps[j])
	c = 0
	for i in ps:
		c += i // gd - 1
	return c
for _ in range(int(input())):
	print(fun(int(input())))


from math import gcd
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	n = len(arr)
	g = arr[1] - arr[0]
	for i in range(1, n):
		g = gcd(g, arr[i] - arr[i - 1])
	g = gcd(g, 360 - arr[n - 1] + arr[0])
	count = 0
	for i in range(1, n):
		count += (arr[i] - arr[i - 1]) // g - 1
	count += (360 - arr[n - 1] + arr[0]) // g - 1
	print(count)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	ang = list(map(int, a.split()))
	sec = []
	for j in range(1, n):
		sec.append(ang[j] - ang[j - 1])
	sec.append(360 + ang[0] - ang[n - 1])
	fihc = gcd(sec[0], sec[1])
	for j in range(2, n):
		fihc = gcd(fihc, sec[j])
	tose = 0
	for j in range(n):
		tose = tose + sec[j] // fihc - 1
	print(tose)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	l = [int(y) for y in input().split(' ')]
	g = l[1] - l[0]
	count = 0
	for i in range(1, n):
		g = gcd(g, l[i] - l[i - 1])
	g = gcd(g, 360 - l[n - 1] + l[0])
	for i in range(1, n):
		count += (l[i] - l[i - 1]) // g - 1
	count += (360 - l[n - 1] + l[0]) // g - 1
	print(count)


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

def gcd_of_list(lst):
	a = lst[0]
	for item in lst:
		a = gcd(item, a)
		if a == 1:
			return 1
	return a

def __starting_point():
	cases = int(input())
	for _ in range(cases):
		cuts = int(input())
		angles = list(map(int, input().split()))
		min_angle = angles[0]
		size = []
		for i in range(cuts):
			if i != cuts - 1:
				size.append(angles[i + 1] - angles[i])
		size.append(360 - angles[-1] + angles[0])
		diff = gcd_of_list(size)
		print(360 // diff - len(size))
__starting_point()


import math

def gcd_list(numbers):
	result = numbers[0]
	for i in range(1, len(numbers)):
		result = math.gcd(result, numbers[i])
	return result
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().strip().split()]
	if a[0] > 0:
		b = a[0]
		for i in range(n):
			a[i] -= b
	a.append(360)
	b = []
	for i in range(n):
		b.append(a[i + 1] - a[i])
	c = gcd_list(b)
	ans = 0
	for i in b:
		ans += i // c - 1
	print(ans)


import math
t = input()
for c in range(0, int(t)):
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	ans = a[1] - a[0]
	for i in range(1, n):
		l.append(a[i] - a[i - 1])
		ans = math.gcd(ans, l[-1])
	l.append(360 - a[-1] + a[0])
	ans = math.gcd(ans, l[-1])
	ans = 360 // ans
	print(ans - n)


import math
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	a = l[1] - l[0]
	for j in range(2, n):
		a = math.gcd(a, l[j] - l[j - 1])
	a = math.gcd(a, 360 - l[-1] + l[0])
	b = 360 / a
	if b == int(b):
		print(int(b) - n)
	else:
		print(360 - n)


import math
t = eval(input())
for g in range(t):
	p = eval(input())
	str = input()
	l = str.split()
	a = int(l[0])
	for x in range(len(l)):
		l[x] = int(l[x]) - a
	a = int(l[0])
	for x in range(1, len(l)):
		a = math.gcd(a, l[x])
	a = math.gcd(a, 360)
	num = 0
	for x in range(a, 360, a):
		if x not in l:
			num += 1
	print(num)


t = int(input())
for x in range(t):
	cu = int(input())
	angle = list(map(int, input().split()))
	diff = []
	mi = float('infinity')
	for i in range(cu - 1):
		diff.append(angle[i + 1] - angle[i])
		if diff[i] < mi:
			mi = diff[i]
	diff.append(angle[0] - angle[cu - 1] + 360)
	if diff[cu - 1] < mi:
		mi = diff[cu - 1]
	div = 1
	while div < 360:
		smallest = mi / div
		count = 0
		flag = True
		for i in diff:
			dm = divmod(i, smallest)
			if dm[1] != 0:
				flag = False
				break
			count += dm[0]
		if flag:
			print(int(count - cu))
			break
		div += 1


t = int(input())

def gcd(a, b):
	if a < b:
		a = a + b
		b = a - b
		a = a - b
	if a % b == 0:
		return b
	else:
		c = a % b
		return gcd(b, c)
for _ in range(t):
	n = int(input())
	angle_list = list(map(int, input().split()))
	slice_list = []
	for i in range(n):
		if i == n - 1:
			theta = angle_list[0] + 360 - angle_list[i]
		else:
			theta = angle_list[i + 1] - angle_list[i]
		slice_list.append(theta)
	for i in range(n - 1):
		slice_list[1] = gcd(slice_list[0], slice_list[1])
		slice_list.pop(0)
	slices = 360 / slice_list[0] - n
	print(str(int(slices)))


from math import *
from functools import *

def find_gcd(l):
	x = reduce(gcd, l)
	return x
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(d) for d in input().split()]
	l = []
	for i in range(n):
		if abs(a[i] - a[i - 1]) > 180:
			l.append(360 - abs(a[i] - a[i - 1]))
		else:
			l.append(abs(a[i] - a[i - 1]))
	each_angle = find_gcd(l)
	if 360 % each_angle == 0:
		total_cuts = 360 // each_angle
		reqd_cuts = total_cuts - n
		print(reqd_cuts)
	else:
		a1 = gcd(360, each_angle)
		total_cuts = 360 // a1
		reqd_cuts = total_cuts - n
		print(reqd_cuts)


T = int(input())

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for i in range(T):
	N = int(input())
	arrst = input()
	arr = list(map(int, arrst.split()))
	count = 0
	arr.sort()
	lis = [arr[0] - arr[len(arr) - 1] + 360]
	for j in range(len(arr) - 1):
		lis += [arr[j + 1] - arr[j]]
	ans = lis[0]
	for j in range(len(arr)):
		ans = gcd(ans, lis[j])
	for j in range(len(arr)):
		count += lis[j] // ans - 1
	print(int(count))


def hcfnaive(a, b):
	if b == 0:
		return abs(a)
	else:
		return hcfnaive(b, a % b)
for t in range(int(input())):
	n = int(input())
	m = 360
	if 361 > n > 1:
		p = list(map(int, input().split()))
		for i in range(1, n):
			m = min(m, p[i] - p[i - 1])
	x = 360 - m
	t = hcfnaive(m, x)
	t = int(360 / t)
	print(t - n)


def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
T = int(input())
for i in range(T):
	N = int(input())
	lst = [int(x) for x in input().strip().split()]
	diff = []
	for j in range(1, len(lst)):
		diff.append(lst[j] - lst[j - 1])
	diff.append(360)
	gcd = find_gcd(diff[0], diff[1])
	for j in range(2, len(diff)):
		gcd = find_gcd(gcd, diff[j])
	print(360 // gcd - N)


def gcd(a, b):
	if min(a, b) == 0:
		return max(a, b)
	else:
		return gcd(max(a, b) % min(a, b), min(a, b))
t = int(input())
for i in range(t):
	g = 0
	o = []
	n = int(input())
	l = list(map(int, input().split()))
	for j in range(n - 1):
		o.append(l[j + 1] - l[j])
		g = gcd(g, o[j])
	g = gcd(g, 360 + l[0] - l[-1])
	print(int(360 / g - len(l)))


def gcd(n1, n2):
	m = 1
	di = 2
	while di <= min(n1, n2) and (n1 > 1 and n2 > 1):
		if n1 % di == 0 and n2 % di == 0:
			n1 //= di
			n2 //= di
			m *= di
		else:
			di += 1
	return m
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(mi, d) = (a[1] - a[0], [a[1] - a[0]])
	for i in range(2, n):
		d += [a[i] - a[i - 1]]
		if d[i - 1] % mi != 0:
			mi = gcd(mi, d[i - 1])
	d += [360 - a[n - 1] + a[0]]
	if d[n - 1] % mi != 0:
		mi = gcd(mi, d[n - 1])
	print(360 // mi - n)


import math
for _ in range(int(input())):
	angels = []
	dif = []
	gcd = 360
	nAngels = int(input())
	angels = list(map(int, input().split()))
	for i in range(1, len(angels)):
		dif.append(angels[i] - angels[i - 1])
	dif.append(angels[0] + (360 - angels[-1]))
	for d in dif:
		gcd = math.gcd(gcd, d)
	print(int(360 / gcd) - nAngels)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if sum(l) == 361:
		print(0)
	else:
		d = list()
		for i in range(1, n):
			d.append(l[i] - l[i - 1])
		d.sort()
		k = d[0]
		x = l[0]
		i = 0
		count = 0
		while True:
			x = x + k
			if i == 0:
				f = x
			if x >= 360:
				x -= 360
			if x == l[0] or (i == 1 and x == f):
				break
			count += 1
			i = 1
		print(count - n + 1)


def compute_gcd(a, b):
	if b == 0:
		return a
	else:
		return compute_gcd(b, a % b)
T = int(input())
while T:
	n = int(input())
	a = list(map(int, input().split()))
	diff = a[1] - a[0]
	gcd = diff
	for i in range(1, n):
		if i == n - 1:
			diff = 360 - a[n - 1] + a[0]
		else:
			diff = a[i + 1] - a[i]
		gcd = compute_gcd(max(diff, gcd), min(diff, gcd))
	min_cuts = int(360 / gcd) - n
	print(min_cuts)
	T -= 1


from functools import reduce
from math import gcd
for _ in range(int(input())):
	num = int(input())
	cuts = list(map(int, input().split(' ')))
	initial_cuts = [0] * (num - 1)
	for i in range(0, num - 1):
		initial_cuts[i] = cuts[i + 1] - cuts[i]
	initial_cuts.append(360)
	red = reduce(gcd, initial_cuts)
	total_initial = int(360 / red)
	vasya_cuts = total_initial - num
	print(vasya_cuts)


def giveDivisors(number):
	ans = []
	for i in range(1, int(number ** 0.5) + 1):
		if number % i == 0:
			if number / i == i:
				ans.append(i)
			else:
				ans.append(i)
				ans.append(number // i)
	ans.sort()
	if ans == [1, number] or ans == [number, 1]:
		return False
	return ans
import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	diff_arr = []
	for i in range(1, n):
		diff_arr.append(arr[i] - arr[i - 1])
	thegcd = diff_arr[0]
	for i in diff_arr:
		thegcd = math.gcd(thegcd, i)
	if 360 % thegcd == 0:
		print(abs(int(360 / thegcd) - n))
	else:
		validDivisors = giveDivisors(thegcd)
		for i in range(len(validDivisors) - 1, 0, -1):
			if 360 % validDivisors[i] == 0:
				print(360 // validDivisors[i] - n)
				break


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
for it in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	z = a[1] - a[0]
	for i in range(2, n):
		z = gcd(z, abs(a[i] - a[i - 1]))
	z = gcd(z, 360 - abs(a[n - 1] - a[0]))
	if 360 % z != 0:
		z = 1
	p = 360 // z - n
	print(p)


from math import gcd
from functools import reduce

def n_cuts(x):
	l = len(x)
	if l == 360:
		print(0)
		return
	mini = min(x)
	flag = 0
	for i in range(len(x)):
		if x[i] % mini != 0:
			flag = 1
			break
	if flag == 0:
		if 360 % mini == 0:
			print(360 // mini - l)
			return
	GCD = reduce(gcd, x)
	result = int(360 / GCD)
	print(result - l)
	return
t = int(input())
for i in range(t):
	n = int(input())
	x = list(map(int, input().split(' ')))
	diff = []
	for i in range(1, len(x)):
		diff.append(x[i] - x[i - 1])
	diff.append(360 - x[-1] + x[0])
	n_cuts(diff)


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
t = int(input())
for T in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	ang = []
	for i in range(1, n):
		ang.append(l[i] - l[i - 1])
	ang.append(360 - (l[-1] - l[0]))
	ang.sort()
	if ang == ang[::-1]:
		print(0)
		continue
	g = ang[0]
	for i in range(1, n):
		g = gcd(g, ang[i])
	total = 360 // g - len(ang)
	print(total)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	x = []
	for i in range(1, n):
		x.append(a[i] - a[i - 1])
	x.append(360 - a[n - 1] + a[0])
	p = x[0]
	s = 0
	for i in x:
		p = gcd(p, i)
	for i in x:
		s += i // p - 1
	print(s)


import numpy as np
import math
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	aa = np.zeros([n], dtype=int)
	for i in range(n - 1):
		aa[i] = a[i + 1] - a[i]
	aa[n - 1] = 360 - a[n - 1] + a[0]
	hcf = 180
	for i in range(n):
		hcf = min(hcf, math.gcd(aa[i % n], aa[(i + 1) % n]))
	print(360 // hcf - n)


def isDivisible(a, k):
	for i in a:
		if i % k != 0:
			return False
	return True

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def findHCF(l):
	gcd = find_gcd(l[0], l[1])
	for i in range(2, len(l)):
		gcd = find_gcd(gcd, l[i])
	return gcd

def calDegree(a):
	b = []
	p = a[0]
	i = 1
	while i < len(a):
		b.append((a[i] - p) % 360)
		p = a[i]
		i += 1
	return b

def calRawCount(a, k):
	s = 0
	for i in a:
		s += i // k
	return s
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split(' ')))
	l.append(l[0])
	a = calDegree(l)
	HCF = findHCF(a)
	raw_count = calRawCount(a, HCF)
	print(raw_count - len(l) + 1)


import numpy
import math
from sys import stdin, stdout
from bisect import bisect_left, bisect_right

def pnt(x):
	stdout.write(str(x) + '\n')

def pnt(x, end=' '):
	stdout.write(str(x) + end)

def countSetBits(n):
	count = 0
	while n:
		count += n & 1
		n >>= 1
	return count

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
inp = lambda : int(stdin.readline())
sip = lambda : input()
mulip = lambda : map(int, input().split())
lst = lambda : list(map(int, stdin.readline().split()))
slst = lambda : list(sip())
for _ in range(inp()):
	N = inp()
	A = lst()
	B = []
	for i in range(0, N):
		if i == N - 1:
			B.append(360 + A[0] - A[i])
		else:
			B.append(A[i + 1] - A[i])
	if len(set(B)) == 1:
		print(0)
	else:
		N1 = B[0]
		N2 = B[1]
		g = gcd(N1, N2)
		for i in range(2, len(B)):
			g = gcd(g, B[i])
		x = 360 // g
		print(abs(x - N))


from math import gcd
from functools import reduce
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	slices = [a[i + 1] - a[i] for i in range(n - 1)] + [360 + a[0] - a[n - 1]]
	sliceAngle = gcd(reduce(lambda a, b: gcd(a, b), slices), 360)
	print(360 // sliceAngle - n)


import math
tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	gcd = 0
	for j in range(length - 1):
		gcd = math.gcd(gcd, arr[j + 1] - arr[j])
	gcd = math.gcd(gcd, 360 + arr[0] - arr[-1])
	requried = 360 // gcd
	print(requried - length)


def computeHCF(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
import math
from fractions import gcd
from functools import reduce

def find_gcd(a):
	x = reduce(computeHCF, a)
	return x
T = int(input())
for i in range(T):
	n = int(input())
	array = list(map(int, input().split()))
	array.sort()
	arr = []
	for i in range(n - 1):
		arr.append(array[i + 1] - array[i])
	arr.append(array[0] + 360 - array[n - 1])
	s = find_gcd(arr)
	cnt = 1
	w = array[0]
	g = array[0]
	b = True
	while b:
		if g + s >= 0 and g + s < 360:
			g = g + s
			cnt = cnt + 1
		else:
			g = g + s - 360
			cnt = cnt + 1
		if g == w:
			cnt = cnt - 1
			b = False
			break
	print(cnt - n)


def hcf(a, b):
	if b == 0:
		return a
	else:
		return hcf(b, a % b)
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	b = []
	for j in range(len(a) - 1):
		b.append(a[j + 1] - a[j])
	b.append(360 - a[len(a) - 1] + a[0])
	for k in range(len(b) - 1):
		b[k + 1] = hcf(b[k], b[k + 1])
	p = 360 / b[len(b) - 1]
	print(int(p - len(a)))


def gcd(a, b):
	if a > b:
		return gcd(b, a)
	elif a == 0:
		return b
	return gcd(b % a, a)
t = int(input())
while t:
	n = int(input())
	arr = [int(i) for i in input().split()]
	sarr = []
	for i in range(1, n):
		sarr.append(arr[i] - arr[i - 1])
	g = sarr[0]
	for num in sarr[1:]:
		g = gcd(g, num)
	if 360 % g == 0:
		print(360 // g - n)
	else:
		ans = g
		for i in range(2, g):
			if g % i == 0 and 360 % i == 0:
				ans = i
		if ans != g:
			print(360 // ans - n)
		else:
			print(360 - n)
	t -= 1


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	temp = []
	for i in range(n - 1):
		temp.append(l[i + 1] - l[i])
	temp.append(360 - l[-1] + l[0])
	gc = temp[0]
	for i in range(1, n):
		gc = math.gcd(gc, temp[i])
	print(360 // gc - n)


import math as m
for _ in range(int(input())):
	angels = []
	d = []
	total = 360
	nAngels = int(input())
	angels = list(map(int, input().split()))
	for i in range(1, len(angels)):
		d.append(angels[i] - angels[i - 1])
	d.append(angels[0] + (360 - angels[-1]))
	for j in d:
		total = m.gcd(total, j)
	print(360 // total - nAngels)


import math
T = int(input())
for x in range(T):
	d = []
	g = 360
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(1, n):
		d.append(a[i] - a[i - 1])
	d.append(a[0] + (360 - a[-1]))
	for i in d:
		g = math.gcd(i, g)
	print(int(360 / g) - n)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	a = [int(r) for r in input().split()]
	p = []
	for x in range(n - 1):
		p.append(a[x + 1] - a[x])
	p.append(360 - a[n - 1] + a[0])
	e = p[0]
	for x in range(1, n):
		e = gcd(e, p[x])
	su = 0
	for x in p:
		su += x // e - 1
	print(su)


import math
t = int(input())
for i in range(t):
	a = []
	d = []
	gcd = 360
	n = int(input())
	a = list(map(int, input().split()))
	for j in range(1, len(a)):
		d.append(a[j] - a[j - 1])
	d.append(a[0] + (360 - a[-1]))
	for k in d:
		gcd = math.gcd(gcd, k)
	print(int(360 / gcd) - n)


from math import gcd
T = int(input())
for i in range(T):
	B = []
	Ttl = 0
	N = int(input())
	A = list(map(int, input().split()))
	for i in range(N - 1):
		B.append(A[i + 1] - A[i])
	B.append(A[0] + 360 - A[N - 1])
	J = B[0]
	for i in range(N):
		J = gcd(B[i], J)
	for i in range(N):
		if B[i] // J != 1:
			Ttl += B[i] // J - 1
	print(Ttl)


import math
for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split(' ')))
	d = []
	gcd = 360
	for i in range(n - 1):
		d.append(L[i] - L[i + 1])
	d.append(L[0] + (360 - L[-1]))
	for each in d:
		gcd = math.gcd(gcd, each)
	print(360 // gcd - n)


import math
num_cases = int(input())
for case in range(num_cases):
	num_cuts = int(input())
	angles = list(map(int, input().split()))
	offset = min(angles)
	angles = list(map(lambda a: a - offset, angles))
	remaining_angle = 360 - max(angles)
	angles.append(remaining_angle)
	common_angle = angles[0]
	for cut in range(num_cuts + 1):
		common_angle = math.gcd(common_angle, angles[cut])
	num_cuts_required = int(360 / common_angle)
	print(num_cuts_required - num_cuts)


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(v) for v in input().strip().split()]
	a.sort()
	f = a[1] - a[0]
	j = 2
	while j < n - 1 and f != 1:
		m = a[j + 1] - a[j]
		if m != f:
			f = math.gcd(f, m)
		j = j + 1
	v = math.gcd(360, f)
	ans = int(360 / v) - n
	print(ans)


def hhcf(a):
	hcf = 0
	sm = min(a)
	for i in range(1, sm + 1):
		for j in a:
			if j % i != 0:
				break
		else:
			hcf = i
	return hcf
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	b = []
	for i in range(n - 1):
		b.append(a[i] - a[i + 1])
	b.append(360 - a[0] + a[n - 1])
	h = hhcf(b)
	mi = 360 // h
	print(mi - n)