C. Polygon for the Angle(计算几何,数论)

C. Polygon for the Angle

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an angle angang.

The Jury asks You to find such regular nn-gon (regular polygon with nn vertices) that it has three vertices aa, bb and cc (they can be non-consecutive) with ∠abc=ang∠abc=ang or report that there is no such nn-gon.

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

Input

The first line contains single integer TT (1≤T≤1801≤T≤180) — the number of queries.

Each of the next TT lines contains one integer angang (1≤ang<1801≤ang<180) — the angle measured in degrees.

Output

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

Example

input

Copy

4
54
50
2
178

output

Copy

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 1818-gon. For example, ∠v2v1v6=50∘∠v2v1v6=50∘.

The example angle for the third query is ∠v11v10v12=2∘∠v11v10v12=2∘.

In the fourth query, minimal possible nn is 180180 (not 9090).

解析:

m边形最大为(m-2)*180/m的∠

可以分出(1/(m-2))*x*[(m-2)*180/m]的∠   (1<=x<=m-2),   1~(m-2)    个  180/m  的∠合并

公式:x/m=n/180,(x,n,m都为整数)

结果为:180/gcd(180,n)

但最大∠要大于(m-2)*180/m

所以如果小于,就✖2

ac:

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int gcd(int a,int b){return b==0?a:gcd(b,a%b);}

int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int x=180/gcd(180,n);
        if(n>((x-2)*180/x))
            cout<<x*2<<endl;
        else cout<<x<<endl;
    }
    return 0;
}