You are given an angle $\text{ang}$. 

The Jury asks You to find such regular $n$-gon (regular polygon with $n$ vertices) that it has three vertices $a$, $b$ and $c$ (they can be non-consecutive) with $\angle{abc} = \text{ang}$ or report that there is no such $n$-gon. [Image] 

If there are several answers, print the minimal one. It is guarantied that if answer exists then it doesn't exceed $998244353$.


-----Input-----

The first line contains single integer $T$ ($1 \le T \le 180$) — the number of queries. 

Each of the next $T$ lines contains one integer $\text{ang}$ ($1 \le \text{ang} < 180$) — the angle measured in degrees. 


-----Output-----

For each query print single integer $n$ ($3 \le n \le 998244353$) — minimal possible number of vertices in the regular $n$-gon or $-1$ if there is no such $n$.


-----Example-----
Input
4
54
50
2
178

Output
10
18
90
180



-----Note-----

The answer for the first query is on the picture above.

The answer for the second query is reached on a regular $18$-gon. For example, $\angle{v_2 v_1 v_6} = 50^{\circ}$.

The example angle for the third query is $\angle{v_{11} v_{10} v_{12}} = 2^{\circ}$.

In the fourth query, minimal possible $n$ is $180$ (not $90$).

Difficulty: interview

Starter code:

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

for T in range(int(input())):
  de=int(input())
  g=gcd(de, 180)
  if int(de/g)==int(180/g)-1:
    print(int(180/g)*2)
  else:
    print(int(180/g))


def func(a,b):
    mini=min(a,b)
    maxi=max(a,b)
    while maxi%mini!=0:
        maxi,mini=mini,maxi%mini
    return a//mini,b//mini
def main():
    count=int(input())
    for x in range(count):
        ang=int(input())
        a,b=func(2*ang,360)
        if a>b-2:
            print(b*2)
        else:
            if b==1:
                print(3)
            elif b==2:
                print(4)
            else:
                print(b)
main()
        


from math import gcd
n = int(input())
for i in range(n):
    k = int(input())
    u = 180//gcd(180,k)
    if u-u*k//180 <2:
        u*=2
    print(u)

T=int(input())
Q=[int(input()) for i in range(T)]

LIST=[None]*181

for i in range(3,361):
    for k in range(1,i-1):
        if 180*k%i==0 and LIST[180*k//i]==None:
            LIST[180*k//i]=i

LIST[180]=-1      
for q in Q:
    print(LIST[q])


t=int(input())
for i in range (t):
    ang = int(input())
    if ang==179:
        print (360)
        continue
    for n in range (3,181):
        if ang*n%180==0 and ang*n//180<n-1:
            print (n)
            break

import sys
from math import gcd
from itertools import groupby as gb
from itertools import permutations as perm
from collections import Counter as C
from collections import defaultdict as dd
sys.setrecursionlimit(10**5)

T = int(input())
for i in range(T):
    ang = int(input())
    g = gcd(ang, 180)
    gg = 180 // g
    a = ang // g
    if gg - a == 1:
        print(gg*2)
    else:
        print(gg)


from math import *
T = int(input())
for i in range(T):
    a = int(input())
    g = gcd(180, a)
    n = 180 // g
    u = (360 + 180 - a-1) // (180 - a)
    n = (u+n-1)//n * n
    print(n)


def compute_gcd(a, b):
  while b:
    a, b = b, a%b
  return a

T = int(input())
while T:
  x = int(input())
  gcd = compute_gcd(180, x)
  if 180%gcd > 0:
    print(-1)
  else:
    n = int(180/gcd)
    if n * gcd == 180:
      y = (x * n) / 180
      if y == n-1:
        n = 2*n
    else:
      n=-1
    print(n)
  T-=1

t = int(input())
for i in range(t):
    a = int(input())
    if a == 180:
        print(-1)
        break
    for j in range(3, 181):
        if a * j % 180 == 0:
            if j - (a * j // 180) == 1:
                j *= 2
            print(j)
            break

for _ in range(int(input())):
	a, b = 180, int(input())
	b = a - b
	if (a - b) % b == b % b:
		a *= 2
	ibo = a
	while b:
		a, b = b, a % b
	print(ibo // a)


import math


for i in range(int(input())):
    angle = int(input()) * 2
    x = math.gcd(angle, 360)
    a, b = angle // x, 360 // x
    while b - a < 2:
        a, b = a * 2, b * 2
    print(b)

import sys

T = int(sys.stdin.readline().strip())
for t in range (0, T):
    ang = int(sys.stdin.readline().strip())
    n = 180
    if ang % 2 == 0:
        ang = ang // 2
        n = n // 2
    if ang % 2 == 0:
        ang = ang // 2
        n = n // 2
    if ang % 5 == 0:
        ang = ang // 5
        n = n // 5
    if ang % 3 == 0:
        ang = ang // 3
        n = n // 3
    if ang % 3 == 0:
        ang = ang // 3
        n = n // 3
    if n == ang + 1:
        n = n * 2
        ang = ang * 2
    print(n)

import math

T = int(input())
for _ in range(T):
    ang = int(input())
    t = math.gcd(ang,180)
    possiblek = ang//t
    possiblen = 180//t
    if possiblek <= possiblen -2:
        print(possiblen)
    else:
        print(possiblen*2)



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

t = int(input())

for i in range(t):
    ang = int(input())
    g = gcd(ang, 180)

    k = (2*g+180-ang-1)//(180-ang)
    print(180//g*k)


n=int(input())
for item in range(n):
    a=int(input())
    for i in range(1,998244353):
        p=1
        if a%(180/i)==0 and (180/i)*(i-2)>=a:
            print(i)
            p=0
            break
    if p==1:
        print(-1)
        
        


def mingon(angle):
    if angle == 90:
        return 4
    elif angle < 90:
        for i in range(1,2*angle +1):
            if 360 % (2*angle/i) == 0:
                return int(360/(2*angle/i))
    else:
        for i in range(2,2*(180-angle) +1):
            if 360 % (2*(180-angle)/i) == 0:
                return int(360/(2*(180-angle)/i))        
        
    
t = int(input())
for i in range(t):
    ang = int(input())
    print(mingon(ang))
            
                


T = int(input())
a = []
for i in range(3, 361):
    a.append(180 / i)

for i in range(T):
    k = int(input())
    for i in range(len(a)):
        if abs(k / a[i] - k // a[i]) < 10**-10 and k != 180 - a[i]:
            print(i + 3)
            break

tc = int(input())
while tc!=0:
    a = int(input())
    n = 3
    tc-=1
    if a==180:
        print("-1")
        continue
    while True:
        z = 180/n
        if a%z==0 and a/z<=n-2:
            break
        n+=1
    print(n)

T=int(input())
ang=[int(input()) for _ in range(T)]
for a in ang:
	for n in range(3,181):
		if(a%(180/n)==0):
			x=a//(180/n)
			if((n-2)>=x):
				print(n)
				break
	else:
		print(360)


l=[]
for i in range(3,361):
	l.append([])
	x=180/i
	for j in range(1,i-1):
		l[-1].append(x*j)

for _ in range(int(input())):
	x=int(input())
	flag=False
	for i in range(len(l)):
		if x in l[i]:
			print(i+3)
			flag=True
			break
	if flag==False:
		print(-1)


ans = [-1 for x in range(180 + 1)]
for i in range(3, 361):
    start = (i - 2) * 180 / i
    if start != int(start):
        continue
    # print(i, start)

    x = (180 - start) / 2

    for j in range(1, i - 1):
        if x * j == int(x * j) and ans[int(x * j)] == -1:
            ans[int(x * j)] = i
            # print(x * j, i)


n = int(input())

for _ in range(n):
    y = int(input())
    print(ans[y])