C. Polygon for the Angle Educational Codeforces Round 57 (Rated for Div. 2)

题意：给你一个角度，让你求出存在此角度的最小正多边形，不存在输出-1；

题解:暴力，看代码注释

代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define int double
signed main(){
    int t;
    cin>>t;
    while(t--){
        int x;
        cin>>x;
        bool ok=0;
        for(int i=3;i<=998244353;i++){//暴力枚举每个正多边形
            int mx=(i-2)*180/i;/*最大内角*/
            int mn=(90-mx/2);/*最小内角*/
            //cout<<mx<<" "<<mn<<endl;
            for(int j=mn;j<=mx;j+=mn){/*依次枚举每一个可能的角,存在的角是等差数列，差是最小内角*/
                if(j==x){
                    ok=1;
                    break;
                }
            }
            if(ok){
                cout<<i<<endl;
                break;
            }
        }
        if(!ok){
            cout<<-1<<endl;
        }

    }
    return 0;
}

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

output

Copy

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