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

T = int(input())

for t in range(T):
	(ang, ) = (int(s) for s in input().split())
	
	print(db[ang])
	
	