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).
#include <bits/stdc++.h>
using namespace std;
int sc(int &x) { return scanf("%d", &x); }
int sc(unsigned int &x) { return scanf("%u", &x); }
int sc(long long &x) { return scanf("%lld", &x); }
int sc(unsigned long long &x) { return scanf("%llu", &x); }
int sc(double &x) { return scanf("%lf", &x); }
int sc(long double &x) { return scanf("%Lf", &x); }
int sc(char *x) { return scanf("%s", x); }
int sc(char &x) { return scanf("%c", &x); }
template <typename T, typename... Args>
void sc(T &v, Args &...args) {
  sc(v);
  sc(args...);
}
void pr(const int &x) { printf("%d", x); }
void pr(const unsigned int &x) { printf("%u", x); }
void pr(const long long &x) { printf("%lld", x); }
void pr(const unsigned long long &x) { printf("%llu", x); }
void pr(const double &x) { printf("%.10lf", x); }
void pr(const long double &x) { printf("%.10Lf", x); }
void pr(const char *const &x) { printf("%s", x); }
void pr(char *const &x) { printf("%s", x); }
void pr(const char &x) { printf("%c", x); }
template <typename T, typename... Args>
void pr(T const &v, Args const &...args) {
  pr(v);
  pr(' ');
  pr(args...);
}
const int N = 100010;
const int M = 1024;
const int mod = 1000000007;
inline void _add(int &a, int b) { a = (a + b) % mod; }
inline void _sub(int &a, int b) { a = (a + mod - b) % mod; }
inline void _mul(int &a, int b) { a = (long long)a * b % mod; }
inline int _Add(int a, int b) { return (a + b) % mod; }
inline int _Sub(int a, int b) { return (a + mod - b) % mod; }
inline int _Mul(int a, int b) { return (long long)a * b % mod; }
template <typename T>
inline void _max(T &a, T b) {
  if (b > a) a = b;
}
template <typename T>
inline void _min(T &a, T b) {
  if (b < a) a = b;
}
int pw(int a, int b) {
  int res(1);
  while (b) {
    if (b & 1) _mul(res, a);
    _mul(a, a);
    b >>= 1;
  }
  return res;
}
int pwM(int a, int b, int m) {
  int res(1);
  while (b) {
    if (b & 1) res = (long long)res * a % m;
    a = (long long)a * a % m;
    b >>= 1;
  }
  return res;
}
const int infi = 2147483647;
const long long infl = 9223372036854775807ll;
const double PI = 3.14159265358979323846;
const int inf = 1000000000 + 100;
int n, m, k, q;
int ans[200];
int main() {
  for (int k = 1, lim = 179; k <= lim; ++k) {
    n = 3;
    while (1) {
      for (int i = 1, lim = n - 2; i <= lim; ++i) {
        if ((k * n) == (180 * i)) {
          ans[k] = n;
          break;
        }
      }
      if (ans[k]) break;
      n++;
    }
  }
  int Case;
  sc(Case);
  for (int ca = 1, lim = Case; ca <= lim; ++ca) {
    sc(k);
    pr(ans[k]), pr("\n");
  }
  return 0;
}
