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 java.util.*;

import java.io.*;

public class Main{

    public static void main(String[] args) {

        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader inp = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver solver = new Solver();
        solver.solve(inp, out);
        out.close();
        
          }



    static class Solver {


        class Node implements Comparable<Node>{
            int i;
            int j;
            long c;
          
            Node(int i,int j,long c)
            {
                this.i=i;
                this.j=j;
                this.c=c;
                

            }

           public int compareTo(Node n)
            {
                return Long.compare(this.c, n.c);
            }
        }

        public boolean done(int[] sp,int[] par)
        {
            int root;

            root=findSet(sp[0],par);
            
           for(int i=1;i<sp.length;i++)
           {
                if(root!=findSet(sp[i], par))
                    return false;
           }
           return true;
        }
       public int findSet(int i,int[] par)
       {
           int x =i;
            boolean flag =false;
            while(par[i]>=0)
            {
                flag = true;
                i=par[i];
            }
            if(flag)
                par[x]=i;
            return i;
       }

       public void unionSet(int i,int j,int[] par)
       {
            int x = findSet(i, par);
            int y = findSet(j, par);
            if(x<y)
            {
                par[y]=x;
            }
            else
            {
                par[x]=y;
            }
       }

       public  long pow(long a, long b, long MOD) {
            if (b == 0) {
                return 1;
            }
            if (b == 1) {
                return a;
            }
            long val = pow(a, b / 2, MOD);
            if (b % 2 == 0) {
                return val * val % MOD;
            } else {
                return val * (val * a % MOD) % MOD;

            }
           
        }


        public void minPrimeFactor(int n,int[] s)
        {
            boolean prime[] = new boolean[n+1];
            Arrays.fill(prime, true);
            s[1]=1;
            s[2]=2;
            for(int i=4;i<=n;i+=2)
            {
                prime[i]=false;
                s[i]=2;
            }

            for(int i=3;i<=n;i+=2)
            {
                if(prime[i])
                {
                    s[i]=i;
                    for(int j=2*i;j<=n;j+=i)
                    {
                        prime[j]=false;
                        s[j]=i;
                    }
                }
            }
            
        }

        
        // public void findAllPrime(int n,ArrayList<Node> al,int s[])
        // {
        //     int curr = s[n];
        //     int cnt = 1;
        //     while(n>1)
        //     {
        //         n/=s[n];
        //         if(curr==s[n])
        //         {
        //             cnt++;
        //             continue;

        //         }
        //         Node n1 = new Node(curr,cnt);
        //         al.add(n1);

        //         curr=s[n];
        //         cnt=1;
        //     }
        // }

        

        public int binarySearch(int n,int k)
        {
            int left=1;
            int right=100000000+5;
            int ans=0;
            while(left<=right)
            {
                int mid = (left+right)/2;
                if(n/mid>=k)
                {
                    left = mid+1;
                    ans=mid;
                }
                else
                {
                    right=mid-1;
                }
            }

            return ans;
        }
        public boolean checkPallindrom(String s)
        {
            char ch[] = s.toCharArray();

            for(int i=0;i<s.length()/2;i++)
            {
                if(ch[i]!=ch[s.length()-1-i])
                    return false;
            }
            return true;
        }


        public void dfs_util(ArrayList<Integer>[] al,boolean vis[],int x,int cnt[],int sts[],int fts[],ArrayList<Integer> fi)
        {
               vis[x] = true;
               fi.add(x);
                sts[cnt[0]]=x+1;
                boolean flag = false;
                for(int i=0;i<al[x].size();i++)
                {
                    if(!vis[al[x].get(i)])
                    {   flag =true;
                        cnt[0]++;
                        dfs_util(al, vis, al[x].get(i),cnt,sts,fts,fi);
                    }    
                    
                }
            
            cnt[0]++;
            fts[cnt[0]]=x+1;
            return;
        }

        public void dfs(ArrayList[] al,int sts[],int fts[],ArrayList<Integer> fi)
        {
            int count[]=new int[1];
            count[0]=0;
           boolean vis[] = new boolean[al.length];
           for(int i=0;i<al.length;i++)
           {
                if(!vis[i])
                {
                    count[0]++;
                    dfs_util(al,vis,i,count,sts,fts,fi);
                }
           }
        }
   
        public void remove(ArrayList<Integer>[] al,int x)
        {
            for(int i=0;i<al.length;i++)
            {
                for(int j=0;j<al[i].size();j++)
                {

                    if(al[i].get(j)==x)
                        al[i].remove(j);

                }
            }
        }

        public double gcd(double a, double b) 
        { 
            if (a == 0) 
                return b; 
            return gcd(b % a, a); 
        }

        private void solve(InputReader inp, PrintWriter out1) {
             
                int t = inp.nextInt();
                for(int j=0;j<t;j++)
                {
                    boolean flag = false;
                    long an = inp.nextLong();
                    for(long i=2;i<=998244353;i++)
                    {
                        double c = (180)/(double)i;
                        if(an%c<=0)
                        {
                            double l = ((i-2)*180)/i;
                            if(an>l)
                            {
                                out1.println(2*i);
                            }
                            else
                            {
                                out1.println(i);
                            }
                            flag = true;
                            break;
                        } 
                    }
                    if(!flag)
                    out1.println(-1);
                }
               


        }
}





    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}
class ele{
    long value;
    long i;
    boolean flag;
    public ele(long value,long i)
    {
        this.value = value;
        this.i=i;
        this.flag = false;
    }
}