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).
a = input()
a = int(a)
content = []
for i in range(a):
    x = input()
    content.append(int(x))
answerdict = [[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], [180, -1]]
for i in content:
    print (answerdict[i-1][1])