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.

Difficulty: interview

Starter code:

Solutions:
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)
##    print(g, ang, total)




# cook your dish here
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))

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)) 


# cook your dish here
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)


# cook your dish here
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)

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)))


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)


# cook your dish here
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)


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)) 

#cut pizza codechef solution
#first try to handle boundary conditions, if n(cuts) = 360, return 0
from math import gcd
from functools import reduce

def n_cuts(x):
 """
    x: list of cuts 

    """
 l = len(x)
 if(l == 360):
  print(0)
  return

 #find minimum difference
 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


 #find gcd
 GCD = reduce(gcd, x)
 result = int(360/GCD)
 print(result-l)
 return



def __starting_point():
 t = int(input()) #number of test cases
 for i in range(t):
  n = int(input()) #not use
  x = list(map(int, input().split(' '))) #x is the cuts list
  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)













__starting_point()

# cook your dish here
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

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))


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 = [0]*360

 for i in a:
  arr[i] = 1
  #arr[(180+i)%360] = 1
 val = 0
 dif = []
 for i in range(0,360):
  if(arr[i] == 1):
   dif.append(i - val)
   #print(i, val)
   val = i
 #print(val, dif[0])    
 #print(arr)        
 dif[0] = 360 - (val - dif[0])
 dif.append(360)
 #print(dif)
 q = reduce(gcd, (dif))
 needed = 360/q
 print(int(needed - n))


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)
 
  


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()

# cook your dish here
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 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()

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)) 
 



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)


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 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)

# cook your dish here
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)

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)