Codeforces Round 57- Bài 3

Bài 3: You are given an angle $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}=ang$ or report that there is no such $n-gon$

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 $ang(1\le ang<180)$— the angle measured in degrees.

Output

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

Example

input

Copy

4
54
50
2
178

output

Copy

10
18
90
180

Solution: 

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,g,t;
cin>>t;
for(int i=0;i<t;i++){
cin>>n;
g=__gcd(n,180);
int k=n/g;
n=180/g;
if(k==n-1){n*=2;}cout<<n<<endl;
}}