Problem: 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.

<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 ≤ T ≤ 180) — the number of queries. 

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

Output

For each query print single integer n (3 ≤ n ≤ 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).

Solution (in JAVA):

Solution:
import javafx.scene.layout.Priority;

import java.io.*;
import java.lang.reflect.Array;
import java.net.Inet4Address;
import java.util.*;
import java.lang.*;
import java.util.HashMap;
import java.util.PriorityQueue;
public class templ implements Runnable {
    public class triplet implements Comparable
    {
        int f,s;
        long t;
        triplet(int f,int s,long t)
        {
            this.f=f;
            this.s=s;
            this.t=t;
        }
        public boolean equals(Object o)
        {
            triplet ob=(triplet)o;
            int ff,ss;
            long tt;
            if(o!=null)
            {
                ff=ob.f;
                ss=ob.s;
                tt=ob.t;
                if((ff==this.f)&&(ss==this.s)&&(tt==this.t))
                    return true;
            }
            return false;
        }
        public int hashCode()
        {
            return (this.f+" "+this.s+" "+this.t).hashCode();
        }
        public int compareTo(Object o)
        {
            triplet tr=(triplet)o;
            if(t>tr.t)
                return 1;
            else
                return -1;
        }
    }
    public class pair implements Comparable
    {
        int f;
        int s;
        pair(int f,int s)
        {
            this.f=f;
            this.s=s;
        }
        public boolean equals(Object o)
        {
            pair ob=(pair)o;
            int ff;
            int ss;
            if(o!=null)
            {
                ff=ob.f;
                ss=ob.s;
                if((ff==this.f)&&(ss==this.s))
                    return true;
            }
            return false;
        }
        public int hashCode()
        {
            return (this.f+" "+this.s).hashCode();
        }
        public int compareTo(Object o)
        {
            pair pr=(pair)o;
            if(s>pr.s)
                return 1;
            else if(s==pr.s)
            {
                if(f<pr.f)
                    return -1;
                else
                    return 1;
            }
            else
                return -1;
        }
    }
    int lazy[],d[];
    long tree[];
    void update(int node,int start,int end,int l,int r)
    {
        if(lazy[node]!=0)
        {
            if(start==end)
            {
                tree[node]=tree[node]+(long)d[start]*lazy[node];
            }
            if(start!=end)
            {
                tree[node]+=lazy[node];
                lazy[2*node]+=lazy[node];
                lazy[2*node+1]+=lazy[node];
            }
            lazy[node]=0;
        }
        if(start>r||l>end)
            return;
        if(start>=l&&end<=r)
        {
            if(start==end)
            {
                tree[node]+=d[start];
            }
            if(start!=end)
            {
                tree[node]+=1;
                lazy[2*node]+=1;
                lazy[2*node+1]+=1;
            }
            return;
        }
        int mid=(start+end)/2;
        update(2*node,start,mid,l,r);
        update(2*node+1,mid+1,end,l,r);
        tree[node]=Math.min(tree[2*node],tree[2*node+1]);
    }
    void update1(int node,int start,int end,int idx,int val)
    {
        if(lazy[node]!=0)
        {
            if(start==end)
            {
                tree[node]=tree[node]+(long)d[start]*lazy[node];
            }
            if(start!=end)
            {
                tree[node]+=lazy[node];
                lazy[2*node]+=lazy[node];
                lazy[2*node+1]+=lazy[node];
            }
            lazy[node]=0;
        }
        if(idx<start||idx>end)
            return;
        if(start==end)
        {
            tree[node]+=val;
            return;
        }
        int mid=(start+end)/2;
        update1(2*node,start,mid,idx,val);
        update1(2*node+1,mid+1,end,idx,val);
        tree[node]=Math.min(tree[2*node],tree[2*node+1]);
    }
    long query(int node,int start,int end,int idx)
    {
        if(lazy[node]!=0)
        {
            if(start==end)
            {
                tree[node]=tree[node]+(long)d[start]*lazy[node];
            }
            if(start!=end)
            {
                tree[node]+=lazy[node];
                lazy[2*node]+=lazy[node];
                lazy[2*node+1]+=lazy[node];
            }
            lazy[node]=0;
        }
        if(idx<start||idx>end)
            return Long.MAX_VALUE/10;
        if(start==end)
            return tree[node];
        int mid=(start+end)/2;
        long x=query(2*node,start,mid,idx);
        long y=query(2*node+1,mid+1,end,idx);
        return Math.min(x,y);
    }
    public int justsmall(long a[],int l,int r,long x,long val)
    {
        int p=-1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if((a[mid]-val)<=x)
            {
                p=mid;
                l=mid+1;
            }
            else
                r=mid-1;
        }
        return p;
    }
    public static void main(String args[])throws Exception
    {
        new Thread(null,new templ(),"templ",1<<27).start();
    }
    public void run() {
        try {
            InputReader in = new InputReader(System.in);
            PrintWriter out = new PrintWriter(System.out);
            int t=in.ni();
            while(t--!=0)
            {
                int xx=in.ni();
                int ans=-1;
                for(int i=3;i<=360;i++)
                {
                    int sum_of_ang=(i-2)*180;
                    double one_ang=(double)sum_of_ang/i;
                    double ele_ang=one_ang/(i-2);
                    double x=0;
                    for(int j=1;j<=i-2;j++)
                    {
                        x+=ele_ang;
                        if(Math.abs(xx-x)<=0.00001)
                        {
                            ans=i;
                            break;
                        }
                    }
                    if(ans!=-1)
                        break;
                }
                out.println(ans);
            }
            out.close();
        }
        catch(Exception e){
            return;
        }
    }
    static class InputReader {

        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int ni() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nl() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int[] nextIntArray(int n) {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

    }
}