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).
d={1: 180, 2: 90, 3: 60, 4: 45, 5: 36, 6: 30, 7: 180, 8: 45, 9: 20, 10: 18, 11: 180, 12: 15, 13: 180, 14: 90, 15: 12, 16: 45, 17: 180, 18: 10, 19: 180, 20: 9, 21: 60, 22: 90, 23: 180, 24: 15, 25: 36, 26: 90, 27: 20, 28: 45, 29: 180, 30: 6, 31: 180, 32: 45, 33: 60, 34: 90, 35: 36, 36: 5, 37: 180, 38: 90, 39: 60, 40: 9, 41: 180, 42: 30, 43: 180, 44: 45, 45: 4, 46: 90, 47: 180, 48: 15, 49: 180, 50: 18, 51: 60, 52: 45, 53: 180, 54: 10, 55: 36, 56: 45, 57: 60, 58: 90, 59: 180, 60: 3, 61: 180, 62: 90, 63: 20, 64: 45, 65: 36, 66: 30, 67: 180, 68: 45, 69: 60, 70: 18, 71: 180, 72: 5, 73: 180, 74: 90, 75: 12, 76: 45, 77: 180, 78: 30, 79: 180, 80: 9, 81: 20, 82: 90, 83: 180, 84: 15, 85: 36, 86: 90, 87: 60, 88: 45, 89: 180, 90: 4, 91: 180, 92: 45, 93: 60, 94: 90, 95: 36, 96: 15, 97: 180, 98: 90, 99: 20, 100: 9, 101: 180, 102: 30, 103: 180, 104: 45, 105: 12, 106: 90, 107: 180, 108: 5, 109: 180, 110: 18, 111: 60, 112: 45, 113: 180, 114: 30, 115: 36, 116: 45, 117: 20, 118: 90, 119: 180, 120: 6, 121: 180, 122: 90, 123: 60, 124: 45, 125: 36, 126: 10, 127: 180, 128: 45, 129: 60, 130: 18, 131: 180, 132: 15, 133: 180, 134: 90, 135: 8, 136: 45, 137: 180, 138: 30, 139: 180, 140: 9, 141: 60, 142: 90, 143: 180, 144: 10, 145: 36, 146: 90, 147: 60, 148: 45, 149: 180, 150: 12, 151: 180, 152: 45, 153: 20, 154: 90, 155: 36, 156: 15, 157: 180, 158: 90, 159: 60, 160: 18, 161: 180, 162: 20, 163: 180, 164: 45, 165: 24, 166: 90, 167: 180, 168: 30, 169: 180, 170: 36, 171: 40, 172: 45, 173: 180, 174: 60, 175: 72, 176: 90, 177: 120, 178: 180, 179: 360}
t=int(input())
for i in range(t):
    n=int(input())
    print(d[n])