Description

给定一个角度 \(\theta\)，请你寻找一个正 \(n\) 边型，满足在这个正 \(n\) 边型上找三个顶点 \(A,B,C\) （可以不相邻），使得 \(\angle ABC~=~\theta\) 。请输出最小的 \(n\)。保证 \(n\) 不超过 \(998244353\)。多组数据。

注意给出的 \(\theta\) 是使用角度制表示的。

Input

第一行是数据组数 \(T\)

下面 \(T\) 行，每行一个整数 \(\theta\)，代表给出的角度

Output

对于每组数据输出一行代表答案

Hint

\(1~\leq~T~\leq~180~,~1~\leq~\theta~<~180\)。

Solution

多边形内角和定理：

对于一个有 \(n\) 个顶点的凸多边形 \(n~\geq~3\)，其内角和为 \((n~-~2)~\times~180^\circ\)。

证明略。这大概是初中定理吧……大概方法是显然一个 \(n\) 边型可以分成 \((n~-~2)\) 个三角形，每个三角形的内角和是 \(180^\circ\)。至于证明可以分成 \((n~-~2)\) 个三角形，对 \(n\) 做数学归纳即可。

由于这是一个正 \(n\) 边型，所以一个角的度数为 \(\frac{n-2}{n}~\times~180^\circ\)

同时它连向其他每个顶点的线段平分这个角，所以它连向相邻两个顶点的线段组成的角的度数为 \(\frac{n-2}{(n-2)n}~\times~180^\circ~=~\frac{1}{n}~\times~180^\circ\)

我们设选择的点 \(A\) 和点 \(C\) 中间相隔了 \((k-1)\) 个顶点 \((k~\leq~n~-~2)\)，于是这些一共组成了 \(k\) 个角度如上的角。列得方程如下（角度略去）：

\[\frac{k}{n}~\times~180~=~\theta\]

移项得

\[k~\times~180~=~\theta~\times~n\]

我们设 \(s~=~\gcd(\theta~,~180)\)，然后等式两侧同除 \(s\)，得

\(\frac{180}{s}~\times~k~=~\frac{\theta}{s}~\times~n\)

由于\(\frac{180}{s}~\perp~\frac{\theta}{s}\)，所以 \(k~=~\frac{\theta}{s}~,~n~=~\frac{180}{s}\)

考虑这种情况下我们要求 \(k~\leq~n~-~2\)，但是如果算出来不是这样怎么办：如果答案为 \(n\) 时满足上式，则答案为 \(xn(x~\in~Z^+)\) 时一定也满足上式。于是我们不断加 \(n\) 直到合法即可。

Code

#include 
    
     #ifdef ONLINE_JUDGE#define freopen(a, b, c)#endif#define rg register#define ci const int#define cl const long longtypedef long long int ll;namespace IPT {    const int L = 1000000;    char buf[L], *front=buf, *end=buf;    char GetChar() {        if (front == end) {            end = buf + fread(front = buf, 1, L, stdin);            if (front == end) return -1;        }        return *(front++);    }}template 
     
      inline void qr(T &x) {    rg char ch = IPT::GetChar(), lst = ' ';    while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar();    while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar();    if (lst == '-') x = -x;}template 
      
       inline void ReadDb(T &x) {    rg char ch = IPT::GetChar(), lst = ' ';    while ((ch > '9') || (ch < '0')) lst = ch, ch = IPT::GetChar();    while ((ch >= '0') && (ch <= '9')) x = x * 10 + (ch ^ 48), ch = IPT::GetChar();    if (ch == '.') {        ch = IPT::GetChar();        double base = 1;        while ((ch >= '0') && (ch <= '9')) x += (ch ^ 48) * ((base *= 0.1)), ch = IPT::GetChar();    }    if (lst == '-') x = -x;}namespace OPT {    char buf[120];}template 
       
        inline void qw(T x, const char aft, const bool pt) {    if (x < 0) {x = -x, putchar('-');}    rg int top=0;    do {OPT::buf[++top] = x % 10 + '0';} while (x /= 10);    while (top) putchar(OPT::buf[top--]);    if (pt) putchar(aft);}const int maxn = 200010;const int MOD = 998244353;int n;ll ans;char MU[maxn];int main() {    freopen("1.in", "r", stdin);    qr(n);    for (rg int i = 1; i <= n; ++i) do {MU[i] = IPT::GetChar();} while ((MU[i] > 'z') || (MU[i] < 'a'));    MU[0] = MU[1]; MU[n + 1] = MU[n];;    int pos = n; while (MU[pos] == MU[0]) --pos;    int k = n - pos;    for (rg int i = 1; i <= n; ++i) if (MU[i] == MU[i - 1]) {        ++ans;    } else break;    ans = (ans * k) % MOD;    ++ans;    for (rg int i = 1; i <= n; ++i) if (MU[i] == MU[i - 1]) ++ans; else break;    for (rg int i = n; i; --i) if (MU[i] == MU[i + 1]) ++ans; else break;    qw(ans % MOD, '\n', true);    return 0;}