We define a $hackonacci$ series as follows:

$hackonacci(n)=1\cdot hackonacci(n-1)+2\cdot hackon acesi(n-2)+3\cdot hackon aci(n-3)$   
$hackonacci(1)=1$  
$hackonacci(2)=2$  
$hackonacci(3)=3$  

We define a Hackonacci Matrix to be an $n\times n$ matrix where the rows and columns are indexed from ${1}$ to $n$, and the top-left cell is $(1,1)$. Each cell $(i,j)$ must contains either the character X or the character Y. If $hackonacci((i\cdot j)^2)$ is even, it's X; otherwise, it's Y.

Next, we want to perform ${q}$ queries where each query ${i}$ consists of an integer, ${angle}_i$. Each ${angle}_i$ is a multiple of ${90}$ degrees and describes the angle by which you must rotate the matrix in the clockwise direction. For each ${angle}_i$, we want to count the number of cells that are different after the rotation. For example, the diagram below depicts the $270^{\circ}$ rotation of a Hackonacci Matrix when $n=2$: 

As you can see, there are two cells whose values change after the rotation. Note that we filled each initial cell using the Hackonacci formula given above:

$(1,1)$: $hagonacci((1\cdot1)^2)=hakenacci(1)=1$ 

Because this is an odd number, we mark this cell with a Y.
$(1,2)$: $\begin{equation}\begin{aligned}hackonacci((1\cdot2)^2)&=hackonocci(4)\\ &\Rightarrow1\cdot hagonacci(3)+2\cdot hackonaccci(2)+3\cdot hackonacci(1)\\ &\Rightarrow1\cdot3+2\cdot2+3\cdot1=3+4+3=10\end{aligned}\end{equation}$ 

Because this is an even number, we mark this cell with an X.
$(2,1)$: $hakenacci((2\cdot1)^2)=hakenacci(4)\Rightarrow10$ 

Because this is an even number, we mark this cell with an X.
$(2,2)$: $hakenaci((2\cdot2)^2)=hakenacci(16)\Rightarrow296578$ 

Because this is an even number, we mark this cell with an X.

Given the value of $n$ and ${q}$ queries, construct a Hackonacci Matrix and answer the queries. For each query ${i}$, print an integer on a new line denoting the number of cells whose values differ from the initial Hackonacci Matrix when it's rotated by ${angle}_i$ degrees in the clockwise direction. 

Input Format

The first line contains two space-separated integers describing the respective values of $n$ and ${q}$. 

Each line ${i}$ of the ${q}$ subsequent lines contains an integer denoting ${angle}_i$.

Constraints

$1\leq n\leq2000$  
$1\leq q\leq10^4$  
$0\leq angle_i\leq10^5$  
It is guaranteed that each ${angle}_i$ is multiple of ${90}$ degrees.

Output Format

For each ${angle}_i$, print a single integer on a new line denoting the number of different cells that differ between the initial matrix and the matrix rotated by ${angle}_i$ degrees.

Sample Input 0
4 3
90
180
270

Sample Output 0
10
6
10

Explanation 0

Because $n=4$, we must build a $4\times4$ Hackonacci matrix and then perform $q=3$ queries, shown below. The following diagrams depict each query rotation, and cells whose values changed after performing a rotation are highlighted in orange:

When we perform a $90^{\circ}$ rotation on the matrix, there are $10$ cells whose  values change: 

Thus, we print $10$ on a new line.
When we perform a ${180^{\circ}}$ rotation on the matrix, there are ${6}$ cells whose  values change:
 
Thus, we print ${6}$ on a new line.
When we perform a $270^{\circ}$ rotation on the matrix, there are $10$ cells whose  values change:
 
Thus, we print $10$ on a new line.

Source: hackerrank | Difficulty: MEDIUM
Tags: Matrices


Solutions:
def entry(i, j):
	i = i % 7
	j = j % 7
	p = i * i * j * j % 7
	foo = [1, 1, 0, 1, 0, 0, 1, 1]
	return foo[p]

def rot90(n, i, j):
	return (j, n + 1 - i)
(n, num_probs) = (int(x) for x in input().split())
diff90 = 0
diff180 = 0
for i in range(1, n + 1):
	for j in range(1, n + 1):
		val0 = entry(i, j)
		(i90, j90) = rot90(n, i, j)
		val90 = entry(i90, j90)
		(i180, j180) = rot90(n, i90, j90)
		val180 = entry(i180, j180)
		if val0 != val90:
			diff90 += 1
		if val0 != val180:
			diff180 += 1
for prob in range(num_probs):
	angle = int(input())
	angle = angle % 360
	if angle == 0:
		print(0)
	if angle == 90 or angle == 270:
		print(diff90)
	if angle == 180:
		print(diff180)


import sys
import itertools
import operator
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
HSeries = [1, 1, 0, 1, 0, 0, 1, 1]
matrix = []
for i in range(n):
	l = []
	for j in range(n):
		l.append(HSeries[((i + 1) * (j + 1)) ** 2 % 7])
	matrix.append(l)
flatten = list(itertools.chain(*matrix))
rotnum = [0, -1, -1, -1]
for a0 in range(q):
	angle = int(input().strip()) % 360 // 90
	if rotnum[angle] != -1:
		print(rotnum[angle])
	else:
		rotate = matrix
		for _ in range(angle):
			rotate = [list(t) for t in zip(*rotate[::-1])]
		rotate = list(itertools.chain(*rotate))
		diff = sum(list(map(abs, list(map(operator.sub, flatten, rotate)))))
		print(diff)
		rotnum[angle] = diff


import sys
from time import time

def h_gen():
	(a, b, c) = (1, 2, 3)
	for v in (a, b, c):
		yield v
	while True:
		(a, b, c) = (b, c, a + 2 * b + 3 * c)
		yield c

def hsqr_gen():
	(u, u2) = (1, 1)
	for (i, h) in enumerate(h_gen()):
		if i + 1 == u2:
			yield (u, h)
			u += 1
			u2 = u * u

def r_gen():
	cache = (0, 0, 0, 0, 1, 1, 1)
	yield 1
	while True:
		yield from cache
rcache = (1, 0, 0, 0, 0, 1, 1)

def get_r(n):
	u = (n - 1) % len(rcache)
	return rcache[u]

def get_matrix(n):
	return [[get_r((i + 1) * (j + 1)) for j in range(n)] for i in range(n)]

def rotate_90(m):
	new_m = []
	for r in range(len(m)):
		new_m.append([m[i][r] for i in range(len(m) - 1, -1, -1)])
	return new_m

def test(n):
	for (i, h) in enumerate(h_gen()):
		print(h, end=' ', file=sys.stderr)
		if i == n:
			break
	print(file=sys.stderr)
	for (i, h) in enumerate(hsqr_gen()):
		(_, v) = h
		print(v % 2, end=' ', file=sys.stderr)
		if i == n:
			break
	print(file=sys.stderr)
	for (i, r) in enumerate(r_gen()):
		print(r, end=' ', file=sys.stderr)
		if i == n:
			break
	print(file=sys.stderr)
	for i in range(1, n):
		print(get_r(i), end=' ', file=sys.stderr)
	print(file=sys.stderr)
	m = get_matrix(n)
	print(m, file=sys.stderr)
	m = rotate_90(m)
	print(m, file=sys.stderr)

def get_cache(n):

	def count(m1, m2):
		sm = 0
		for i in range(n):
			for j in range(n):
				sm += m1[i][j] ^ m2[i][j]
		return sm
	m = get_matrix(n)
	mm = [m]
	for _ in range(3):
		mm.append(rotate_90(mm[-1]))
	cache = [0] * len(mm)
	for i in range(1, len(mm)):
		cache[i] = count(mm[0], mm[i])
	return cache

def solve(cache, angle):
	r = angle // 90 % 4
	return cache[r]
tm = time()
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
cache = get_cache(n)
print('cache=%s' % cache, file=sys.stderr)
for a0 in range(q):
	angle = int(input().strip())
	print(solve(cache, angle))
print('time elapsed: %s' % (time() - tm), file=sys.stderr)


import operator
(n, q) = map(int, input().split())
checker = (1, 0, 1, 0, 0, 1, 1)
ar = tuple((tuple((checker[(i * i * j * j - 1) % 7] for i in range(1, n + 1))) for j in range(1, n + 1)))

def rotate(mat):
	return tuple(zip(*reversed(mat)))
changes = [0]
temp = ar
for i in range(3):
	temp = rotate(temp)
	changes.append(sum((sum(map(operator.ne, ar[i], temp[i])) for i in range(n))))
for _ in range(q):
	print(changes[int(input()) // 90 % 4])


def hackonacci(n):
	return [1, 0, 1, 0, 0, 1, 1][(n - 1) % 7]

def solve(n, A):
	M = [[hackonacci((i * j) ** 2) for j in range(1, n + 1)] for i in range(1, n + 1)]
	count = {0: 0, 90: 0, 180: 0, 270: 0}
	for i in range(n):
		for j in range(n):
			count[90] += M[i][j] ^ M[j][n - 1 - i]
			count[180] += M[i][j] ^ M[n - 1 - i][n - 1 - j]
			count[270] += M[i][j] ^ M[n - 1 - j][i]
	return list((count[a % 360] for a in A))
(n, q) = map(int, input().split())
A = list((int(input()) for _ in range(q)))
print('\n'.join(map(str, solve(n, A))))


(n, q) = map(int, input().split())

def hackonacci_fun(i, period=(1, 0, 1, 0, 0, 1, 1)):
	return period[(i - 1) % 7]
hack_matrix = n * n * [0]
for i in range(n):
	hack_matrix[i * n + i] = hackonacci_fun((i + 1) ** 4)
	for j in range(i + 1, n):
		hack_matrix[i * n + j] = hack_matrix[j * n + i] = hackonacci_fun(((i + 1) * (j + 1)) ** 2)
rot90 = rot270 = sum((1 for i in range(n) for j in range(n) if hack_matrix[i * n + j] != hack_matrix[j * n + n - 1 - i]))
rot180 = sum((1 for i in range(n) for j in range(n) if hack_matrix[i * n + j] != hack_matrix[(n - 1 - j) * n + n - 1 - i]))
rot = {0: 0, 90: rot90, 180: rot180, 270: rot270}
for _ in range(q):
	print(rot[int(input()) % 360])


import sys
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
parity_helper = [1, 1, 0, 1, 0, 0, 1]
rot_90 = 0
rot_180 = 0
for i in range(1, n // 2 + 1):
	for j in range(1, n + 1):
		if parity_helper[(i * j) ** 2 % 7] != parity_helper[(j * (1 + n - i)) ** 2 % 7]:
			rot_90 += 1
		if parity_helper[(i * j) ** 2 % 7] != parity_helper[((1 + n - i) * (1 + n - j)) ** 2 % 7]:
			rot_180 += 1
rot_90 = 2 * rot_90
rot_180 = 2 * rot_180
if n % 2 == 1:
	i = n // 2 + 1
	for j in range(1, n + 1):
		if parity_helper[(i * j) ** 2 % 7] != parity_helper[(i * (1 + n - j)) ** 2 % 7]:
			rot_180 += 1
rot = [0, rot_90, rot_180, rot_90]
for a0 in range(q):
	angle = int(input().strip())
	print(rot[int(angle / 90 % 4)])


import sys
res = 'YYXYXXY'
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
ans = dict()
ans[0] = 0
ans[90] = 0
ans[180] = 0
ans[270] = 0

def cc(i, j):
	return res[(i * j) ** 2 % 7]
for i in range(1, n + 1):
	for j in range(1, n + 1):
		c = res[(i * j) ** 2 % 7]
		if c != cc(j, n - i + 1):
			ans[90] += 1
		if c != cc(n - i + 1, n - j + 1):
			ans[180] += 1
		if c != cc(n - j + 1, i):
			ans[270] += 1
for a0 in range(q):
	angle = int(input().strip())
	print(ans[angle % 360])


(n, q) = map(int, input().split())
queries = (int(input()) for _ in range(q))
h = [1, 2, 3]
for _ in range(11):
	h.append(h[-1] + 2 * h[-2] + 3 * h[-3])
h = [i & 1 for i in h]
matrix = bytearray(n ** 2)
k = 0
for i in range(1, n + 1):
	for j in range(1, n + 1):
		matrix[k] = h[((i * j) ** 2 - 1) % 14]
		k += 1
differences = [0, None, None, None]
(ndiv, nmod) = divmod(n, 2)
diff = 0
for i in range(ndiv):
	for j in range(n):
		if matrix[n * i + j] != matrix[n * j + n - 1 - i]:
			diff += 2
if nmod:
	for j in range(n):
		if matrix[n * ndiv + j] != matrix[n * j + n - 1 - ndiv]:
			diff += 1
differences[1] = differences[3] = diff
diff = 0
for i in range(ndiv):
	for j in range(n):
		if matrix[n * i + j] != matrix[n * (n - 1 - j) + n - 1 - i]:
			diff += 2
if nmod:
	for j in range(n):
		if matrix[n * ndiv + j] != matrix[n * (n - 1 - j) + n - 1 - ndiv]:
			diff += 1
differences[2] = diff
for q in queries:
	print(differences[q % 360 // 90])


import sys

def rotated(M):
	res = []
	for r in range(n):
		res.append([])
		for c in range(n):
			res[-1].append(M[n - 1 - c][r])
	return res
Q = [1, 1, 0, 1, 0, 0, 1]
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
M = []
for r in range(1, n + 1):
	M.append([])
	for c in range(1, n + 1):
		M[-1].append(Q[r * r * c * c % 7])
A = {0: 0}
AM = M
for ang in [90, 180, 270]:
	AM = rotated(AM)
	diff = 0
	for r in range(n):
		for c in range(n):
			if AM[r][c] != M[r][c]:
				diff += 1
	A[ang] = diff
for a0 in range(q):
	angle = int(input().strip())
	print(A[angle % 360])


import sys
series = [1, 0, 1, 0, 0, 1, 1]
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]

def rotateMatrix(orgMatrix, i):
	if i == 0:
		return orgMatrix
	elif i == 1:
		return list(zip(*orgMatrix[::-1]))
	elif i == 2:
		orgMatrix = list(zip(*orgMatrix[::-1]))
		return list(zip(*orgMatrix[::-1]))
	elif i == 3:
		orgMatrix = list(zip(*orgMatrix[::-1]))
		orgMatrix = list(zip(*orgMatrix[::-1]))
		return list(zip(*orgMatrix[::-1]))
answer = [None, None, None, None]
orgMatrix = []
for i in range(1, n + 1):
	x = []
	for j in range(1, n + 1):
		x.append(series[(i * j) ** 2 % 7 - 1])
	orgMatrix.append(x)
for a0 in range(q):
	angle = int(input().strip())
	rot = angle % 360 // 90
	if answer[rot] is None:
		altMatrix = rotateMatrix(orgMatrix, rot)
		count = 0
		for i in range(n):
			for j in range(n):
				if orgMatrix[i][j] != altMatrix[i][j]:
					count += 1
		answer[rot] = count
	print(answer[rot])


import sys
(n, q) = map(int, input().strip().split(' '))
memo = ['X', 'X', 'Y', 'Y', 'Y', 'X', 'Y']

def mat(n, memo):
	if n == 1:
		return 'Y'
	elif n == 2:
		return 'X'
	elif n == 3:
		return 'Y'
	else:
		m = (n - 4) % 7
		return memo[m]
arr = []
Nor = {}
final = {0: 0}
for i in range(1, n + 1):
	list1 = []
	for j in range(1, n + 1):
		findnum = (i * j) ** 2
		if findnum not in Nor:
			element = mat(findnum, memo)
			Nor[findnum] = element
			list1.append(element)
		else:
			element = Nor[findnum]
			list1.append(element)
	arr.append(list1)
for i in range(q):
	arr1 = arr
	count = 0
	nmbrturns = int(int(input().strip()) / 90)
	if nmbrturns >= 4:
		nmbrturns = nmbrturns % 4
	if nmbrturns not in final:
		for i in range(nmbrturns):
			Turn = list(zip(*arr1[::-1]))
			arr1 = Turn
		for i in range(n):
			for j in range(n):
				if arr[i][j] != arr1[i][j]:
					count += 1
		final[nmbrturns] = count
		print(count)
	else:
		print(final[nmbrturns])


import sys
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
lookup = [0, 0, 0, 0]
hackonacciEven = [1, 1, 0, 1, 0, 0, 1]

def hackEven(n):
	return hackonacciEven[n % 7]
for i in range(1, n + 1):
	i_ = i % 7
	in_ = (n - i + 1) % 7
	for j in range(1, n + 1):
		j_ = j % 7
		jn_ = (n - j + 1) % 7
		val = hackEven((i_ * j_) ** 2)
		val180 = hackEven((in_ * jn_) ** 2)
		val90 = hackEven((i_ * jn_) ** 2)
		if val != val180:
			lookup[2] = lookup[2] + 1
		if val != val90:
			lookup[1] = lookup[1] + 1
lookup[3] = lookup[1]
for a0 in range(q):
	angle = int(input().strip())
	angle = angle % 360
	print(lookup[angle // 90])


import sys
mat = '*----**\n--**--*\n-*--*-*\n-*--*-*\n--**--*\n*----**\n*******'.splitlines()

def diff(l1, l2):
	flat1 = (item for sublist in l1 for item in sublist)
	flat2 = (item for sublist in l2 for item in sublist)
	ret = 0
	for (a, b) in zip(flat1, flat2):
		if a != b:
			ret += 1
	return ret
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
matrix = []
for row in range(n):
	r = []
	for col in range(n):
		r.append(mat[row % 7][col % 7])
	matrix.append(r)
angle_cache = {0: 0}
for a0 in range(q):
	angle = int(input().strip()) % 360 // 90
	if angle not in angle_cache:
		if angle in (1, 3):
			rotated_matrix = zip(*matrix[::-1])
		if angle == 2:
			rotated_matrix = (x[::-1] for x in matrix[::-1])
		angle_cache[angle] = diff(matrix, rotated_matrix)
	print(angle_cache[angle])


import sys

def hackonacci_is_even(n):
	n = n % 7
	if n == 0:
		return False
	if n == 1:
		return False
	if n == 2:
		return True
	if n == 3:
		return False
	if n == 4:
		return True
	if n == 5:
		return True
	return False

def query(A, angle):
	try:
		return mem[angle]
	except:
		res = 0
		if angle == 90 or angle == 270:
			for i in range(n - 1, -1, -1):
				for j in range(0, n):
					if A[i][j] != A[j][n - 1 - i]:
						res += 1
		elif angle == 180:
			for i in range(n - 1, -1, -1):
				for j in range(n - 1, -1, -1):
					if A[i][j] != A[n - 1 - i][n - 1 - j]:
						res += 1
		mem[angle] = res
		return res
mem = {}
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
A = [[True for i in range(n)] for j in range(n)]
for i in range(0, n):
	for j in range(i, n):
		is_even = hackonacci_is_even(((i + 1) * (j + 1)) ** 2)
		A[i][j] = is_even
		A[j][i] = is_even
for a0 in range(q):
	angle = int(input().strip()) % 360
	print(query(A, angle))


import sys

def hackonacci(num):
	if num == 1:
		return 'Y'
	else:
		r = (num - 1) % 7
		if r in (1, 3, 4):
			return 'X'
		else:
			return 'Y'

def rotate(m, degree):
	if degree == 0:
		return m
	elif degree > 0:
		return rotate(list(zip(*m[::-1])), degree - 90)
	else:
		return rotate(list(zip(*m[::-1])), degree + 90)
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
matrix = []
for i in range(1, n + 1):
	row = []
	for j in range(1, n + 1):
		row.append(hackonacci((i * j) ** 2))
	matrix.append(row)
counts = [0, 0, 0, 0]
flags = [True, False, False, False]
for a0 in range(q):
	abs_angle = int(input().strip()) % 360
	a_idx = abs_angle // 90
	count = 0
	if flags[a_idx]:
		count = counts[a_idx]
	else:
		matrix_rot = list(rotate(matrix, abs_angle))
		for i in range(n):
			rr = list(matrix_rot[i])
			for j in range(n):
				if matrix[i][j] != rr[j]:
					count += 1
		flags[a_idx] = True
		counts[a_idx] = count
	print(count)


def char(i, j):
	i %= 7
	j %= 7
	return [1, 1, 0, 1, 0, 0, 1][i * i * j * j % 7]
qrtr = -1
half = -1
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
N = n + 1
for _ in range(q):
	angle = int(input().strip()) % 360
	if angle == 0:
		print(0)
	elif angle == 180:
		if half < 0:
			half = sum((char(i, j) ^ char(N - i, N - j) for i in range(1, N) for j in range(1, N)))
		print(half)
	else:
		if qrtr < 0:
			qrtr = sum((char(i, j) ^ char(j, N - i) for i in range(1, N) for j in range(1, N)))
		print(qrtr)


from pprint import pprint
is_odd = lambda x: x % 2 != 0
rotate = lambda grid: [tuple(reversed(row)) for row in zip(*grid)]
compare = lambda a, b: sum((sum((a[i][j] != b[i][j] for i in range(n))) for j in range(n)))

def hacko_odd(x):
	if x < 3:
		return x % 2
	else:
		return [1, 0, 0, 1, 1, 1, 0][(x - 3) % 7]
(n, q) = map(int, input().split())
grids = {0: [[hacko_odd((row * col) ** 2) for col in range(1, n + 1)] for row in range(1, n + 1)]}
for deg in range(90, 360, 90):
	grids[deg] = rotate(grids[deg - 90])
results = [0] + [compare(grids[0], grids[deg]) for deg in range(90, 360, 90)]
for _ in range(q):
	print(results[int(input()) % 360 // 90])


import sys
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]

def hack(n):
	n = n % 7
	if n in [2, 4, 5]:
		return 'X'
	else:
		return 'Y'
ans = {0: 0}
for a0 in range(q):
	angle = int(input().strip())
	angle = angle % 360
	if angle in ans.keys():
		print(ans[angle])
	elif angle != 180:
		count = 0
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if hack((i * j) ** 2) != hack(((n - i + 1) * j) ** 2):
					count += 1
		print(count)
		ans[90] = count
		ans[270] = count
	else:
		count = 0
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if hack((i * j) ** 2) != hack(((n - i + 1) * (n - j + 1)) ** 2):
					count += 1
		print(count)
		ans[180] = count


import sys

def hack(n):
	x = 1
	y = 2
	z = 3
	if n == 1:
		return False
	if n == 2:
		return True
	if n == 3:
		return False
	a = [True, True, False, False, False, True, False]
	return a[(n - 4) % 7]
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
ans90 = ans180 = ans270 = 0
hackonaki = [['Y' for x in range(n + 1)] for x in range(n + 1)]
for i in range(1, n + 1):
	for j in range(i, n + 1):
		if hack(i * j * i * j):
			hackonaki[i][j] = 'X'
			hackonaki[j][i] = 'X'
for i in range(1, n + 1):
	for j in range(1, n + 1):
		if hackonaki[i][j] != hackonaki[j][n - i + 1]:
			ans90 += 1
		if hackonaki[i][j] != hackonaki[n - i + 1][n - j + 1]:
			ans180 += 1
		if hackonaki[i][j] != hackonaki[n - j + 1][i]:
			ans270 += 1
res = {}
res[0] = 0
res[90] = ans90
res[180] = ans180
res[270] = ans270
for a0 in range(q):
	angle = int(input().strip())
	angle = angle % 360
	print(res[angle])


import sys

def rotate_90(mat):
	rotated_90 = zip(*mat[::-1])
	return list(rotated_90)

def compare_mat(arr1, arr2):
	res = 0
	nn = len(arr1)
	for i in range(nn):
		for j in range(nn):
			res += int(arr1[i][j] != arr2[i][j])
	return res
FACCO = [1, 1, 0, 1, 0, 0, 1]
FACCO1 = set([0, 1, 3, 6])

def create_mat(n):
	mat = []
	for i in range(n):
		mat.append([0] * n)
	for i in range(n):
		for j in range(i, n):
			ij2 = (i + 1) * (i + 1) * (j + 1) * (j + 1) % 7
			if ij2 in FACCO1:
				mat[i][j] = 1
			if i != j:
				mat[j][i] = mat[i][j]
	return mat

def process(n, angles):
	angles_values_calculated = [0, 0, 0, 0]
	angles_transformed = [ang % 360 for ang in angles]
	angles_to_calculate = set(angles_transformed)
	calculate = True
	if len(angles_to_calculate) == 1 and list(angles_to_calculate)[0] == 0:
		calculate = False
	if calculate:
		mat = create_mat(n)
		mat_angle_90 = rotate_90(mat)
		angles_values_calculated[1] = compare_mat(mat, mat_angle_90)
		mat_angle_180 = rotate_90(mat_angle_90)
		angles_values_calculated[2] = compare_mat(mat, mat_angle_180)
		mat_angle_270 = rotate_90(mat_angle_180)
		angles_values_calculated[3] = compare_mat(mat, mat_angle_270)
	for angle in angles_transformed:
		print(angles_values_calculated[angle // 90])
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
angles = []
for a0 in range(q):
	angle = int(input().strip())
	angles.append(angle)
process(n, angles)


hackonacci = dict()
for i in range(1, 15):
	for j in range(i, 15):
		curr = (i * j) ** 2
		curr %= 7
		h = '1010011'[curr - 1]
		hackonacci[i % 7, j % 7] = h
		hackonacci[j % 7, i % 7] = h
import sys
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
mat = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
	for j in range(i, n):
		mat[i][j] = mat[j][i] = hackonacci[(i + 1) % 7, (j + 1) % 7]
mat_270 = [[mat[n - 1 - i][j] for j in range(n)] for i in range(n)]
mat_180 = [[mat[n - 1 - i][n - 1 - j] for j in range(n)] for i in range(n)]
mat_90 = [[mat[i][n - 1 - j] for j in range(n)] for i in range(n)]
(a1, a2, a3) = (0, 0, 0)
for i in range(n):
	for j in range(n):
		if mat[i][j] != mat_90[i][j]:
			a1 += 1
		if mat[i][j] != mat_180[i][j]:
			a2 += 1
		if mat[i][j] != mat_270[i][j]:
			a3 += 1
for i in range(q):
	angle = int(input()) % 360
	if angle == 0:
		print(0)
	elif angle == 90:
		print(a1)
	elif angle == 180:
		print(a2)
	else:
		print(a3)


import sys
hackonacci_pattern = 'YXYXXYY'

def hackonacci_matrix(rows, cols):
	matrix = []
	for r in range(1, rows + 1):
		row = []
		for c in range(1, cols + 1):
			i = (r * c) ** 2
			row.append(hackonacci_pattern[(i - 1) % 7])
		matrix.append(''.join(row))
	return matrix

def rotate_track(row, col, rows, cols):
	row_end = rows - 1
	col_end = cols - 1
	track = []
	for i in range(col_end):
		track.append((row + 0, col + i))
	for i in range(row_end):
		track.append((row + i, col + col_end))
	for i in range(col_end, 0, -1):
		track.append((row + row_end, col + i))
	for i in range(row_end, 0, -1):
		track.append((row + i, col + 0))
	return track

def rotate(matrix, angle):
	diff_count = 0
	n = len(matrix)
	(row, col) = (0, 0)
	while n > 1:
		L = []
		track = rotate_track(row, col, n, n)
		for (r, c) in track:
			L.append(matrix[r][c])
		i = (n - 1) * (angle // 90)
		R = L[-i:] + L[:-i]
		count = sum((1 for (a, b) in zip(L, R) if a != b))
		diff_count += count
		n -= 2
		row += 1
		col += 1
	return diff_count
(n, q) = (int(v) for v in input().strip().split(' '))
matrix = hackonacci_matrix(n, n)
cache = {}
for a0 in range(q):
	angle = int(input().strip()) % 360
	result = 0
	if angle > 0:
		if angle not in cache:
			cache[angle] = rotate(matrix, angle)
		result = cache[angle]
	print(result)


(n, q) = [int(x) for x in input().split()]
g = []
d = [1, 1, 0, 1, 0, 0, 1, 1]

def pr(l):
	for x in l:
		for y in x:
			print(y, end='')
		print('\r')
	print('\r')
for i in range(1, n + 1):
	g.append([d[i * i * j * j % 7] for j in range(1, n + 1)])

def df(k, l):
	s = 0
	for x in range(n):
		for y in range(n):
			if k[x][y] != l[x][y]:
				s += 1
	return s
g1 = list(zip(*g[::-1]))
o1 = df(g, g1)
g2 = list(zip(*g1[::-1]))
o2 = df(g, g2)
g3 = list(zip(*g2[::-1]))
o3 = df(g, g3)
for a0 in range(q):
	a = int(input().strip())
	a = a % 360
	a = a // 90
	if a == 1:
		print(o1)
	elif a == 2:
		print(o2)
	elif a == 3:
		print(o3)
	else:
		print(0)


import sys
cache = [1, 1, 0, 1, 0, 0, 1]

def hackonacci(n):
	return cache[n % 7]
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
matrix = [[hackonacci(((i + 1) * (j + 1)) ** 2) for i in range(n)] for j in range(n)]
results = [0, None, None, None]
count = 0
for i in range(n):
	for j in range(n):
		count += matrix[i][j] != matrix[j][n - i - 1]
results[1] = count
count = 0
for i in range(n):
	for j in range(n):
		count += matrix[i][j] != matrix[n - i - 1][n - j - 1]
results[2] = count
count = 0
for i in range(n):
	for j in range(n):
		count += matrix[i][j] != matrix[n - j - 1][i]
results[3] = count
for a0 in range(q):
	angle = int(input().strip())
	print(results[angle // 90 % 4])


import sys

def hack(n):
	return [1, 1, 0, 1, 0, 0, 1][n % 7]

def rot(m):
	return list(zip(*m[::-1]))
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
mat = []
for i in range(1, n + 1):
	mat.append([hack((i * j) ** 2) for j in range(1, n + 1)])
diff90 = 0
r = rot(mat)
for i in range(n):
	for j in range(n):
		if mat[i][j] != r[i][j]:
			diff90 += 1
diff180 = 0
r = rot(r)
for i in range(n):
	for j in range(n):
		if mat[i][j] != r[i][j]:
			diff180 += 1
for a0 in range(q):
	angle = int(input().strip()) % 360 // 90
	if angle == 0:
		print(0)
	elif angle == 2:
		print(diff180)
	else:
		print(diff90)


data = [1, 1, 0, 1, 0, 0, 1, 1]
B = []
C = [0, 32]
D = [0, 32]
E = [0, 48]
F = [0, 54]
G = [0, 88]
for i in range(0, 300):
	B.append(30 * i * i)
t1 = 8
t2 = 22
for i in range(2, 300):
	C.append(B[i] - t1)
	t1 += t2
	t2 += 12
t1 = 6
t2 = 10
for i in range(2, 300):
	D.append(C[i] - t1)
	t1 += t2
	t2 += 4
t1 = 28
for i in range(2, 300):
	E.append(D[i] + t1)
	t1 += 12
t1 = 16
t2 = 14
for i in range(2, 300):
	F.append(E[i] + t1)
	t1 += t2
	t2 += 4
t1 = 72
t2 = 50
for i in range(2, 300):
	G.append(F[i] + t1)
	t1 += t2
	t2 += 12

def hack(i):
	return data[i % 7]

def calculate1(n):
	if n == 1:
		return 0
	if n == 2:
		return 2
	if n == 3:
		return 4
	if n == 4:
		return 10
	if n == 5:
		return 14
	n += 1
	x = n // 7
	y = n % 7
	(b, c, d, e, f, g) = (0, 0, 0, 0, 0, 0)
	if y == 0:
		return 0
	b = 24 * x * x
	c = b + x * 4
	d = c + 2 + x * 12
	e = d + 2 + x * 4
	f = e + 6 + x * 10
	g = f + 4 + x * 8
	if y == 1:
		return b
	if y == 2:
		return c
	if y == 3:
		return d
	if y == 4:
		return e
	if y == 5:
		return f
	if y == 6:
		return g

def calculate2(n):
	ans = [0, 0, 2, 6, 6, 14, 0, 30, 32, 32, 48, 54, 88]
	if n <= 12:
		return ans[n]
	n += 1
	x = n // 7
	y = n % 7
	if y == 0:
		return 0
	if y == 1:
		return B[x]
	if y == 2:
		return C[x]
	if y == 3:
		return D[x]
	if y == 4:
		return E[x]
	if y == 5:
		return F[x]
	if y == 6:
		return G[x]

def calculate22(n):
	cnt = 0
	for i in range(n):
		for j in range(n):
			if hack(((n - i) * (n - j)) ** 2) != hack(((j + 1) * (i + 1)) ** 2):
				cnt += 1
	return cnt
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
for a0 in range(q):
	angle = int(input().strip())
	angle = angle % 360
	if angle == 0:
		print(0)
	elif angle == 90:
		print(calculate1(n))
	elif angle == 180:
		print(calculate2(n))
	elif angle == 270:
		print(calculate1(n))


import sys
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
arr = []
arrd = []
h = [0, 0, 0, 0, 1, 1, 1]
a = []
for x in range(n):
	a.append([])
	for y in range(n):
		if h[((x + 1) * (y + 1) - 2) % 7] == 1:
			a[x].append(1)
		else:
			a[x].append(0)
c = {}
c90 = 0
c180 = 0
for x in range(n):
	for y in range(n):
		if a[x][y] + a[x][n - 1 - y] == 1:
			c90 = c90 + 1
		if a[x][y] + a[n - x - 1][n - y - 1] == 1:
			c180 = c180 + 1
c[90] = c90
c[270] = c90
c[180] = c180
c[0] = 0
for a0 in range(q):
	angle = int(input().strip())
	print(c[angle % 360])


import sys
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
period = [1, 0, 1, 0, 0, 1, 1]
block = [[1, 0, 0, 0, 0, 1, 1], [0, 0, 1, 1, 0, 0, 1], [0, 1, 0, 0, 1, 0, 1], [0, 1, 0, 0, 1, 0, 1], [0, 0, 1, 1, 0, 0, 1], [1, 0, 0, 0, 0, 1, 1], [1, 1, 1, 1, 1, 1, 1]]

def hackonacci_parity_bit(n):
	n = (n - 1) % 7
	return period[n]

def hackonacci_matrix(n):
	matrix = [[None] * n for _ in range(n)]
	for i in range(n):
		for j in range(n):
			matrix[i][j] = matrix[j][i] = hackonacci_parity_bit(((i + 1) * (j + 1)) ** 2)
	return matrix

def compare1(mat, n):
	total = 0
	for i in range(n):
		for j in range(n):
			total += mat[i][j] != mat[n - 1 - j][i]
	return total

def compare2(mat, n):
	total = 0
	for i in range(0, n):
		for j in range(i + 1, n):
			total += mat[i][j] != mat[n - 1 - i][n - 1 - j]
	total *= 2
	for i in range(n):
		total += mat[i][i] != mat[n - 1 - i][n - 1 - i]
	return total

def compare3(mat, n):
	total = 0
	for i in range(n):
		for j in range(n):
			total += mat[i][j] != mat[j][n - 1 - i]
	return total
mat = hackonacci_matrix(n)
lst = [0, compare1(mat, n), compare2(mat, n), compare3(mat, n)]
for _ in range(q):
	angle = int(input().strip()) // 90 % 4
	print(lst[angle])


import sys
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
temp = [1, 0, 0, 1, 1, 1, 0]
matrix = [[-1] * n for t in range(n)]
for i in range(n):
	for j in range(n):
		x = ((i + 1) * (j + 1)) ** 2
		if x == 1:
			matrix[i][j] = 1
		elif x == 2:
			matrix[i][j] = 0
		else:
			matrix[i][j] = temp[(x - 2 - 1) % 7]
temp1 = 0
temp2 = 0
temp3 = 0
for i in range(n):
	for j in range(n):
		if matrix[i][j] != matrix[n - j - 1][i]:
			temp1 += 1
		if matrix[i][j] != matrix[n - i - 1][n - j - 1]:
			temp2 += 1
		if matrix[i][j] != matrix[j][n - i - 1]:
			temp3 += 1
for a0 in range(q):
	angle = int(input().strip())
	angle = angle % 360
	if angle == 90:
		print(temp1)
	elif angle == 180:
		print(temp2)
	elif angle == 270:
		print(temp3)
	else:
		print(0)


import sys
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
h = {0: 1, 1: 1, 2: 0, 3: 1, 4: 0, 5: 0, 6: 1}
m = [[h[((i + 1) * (j + 1)) ** 2 % 7] for i in range(n)] for j in range(n)]
r = {}
r[0] = 0
r[90] = sum([sum([int(m[i][j] != m[n - j - 1][i]) for i in range(n)]) for j in range(n)])
r[180] = sum([sum([int(m[i][j] != m[n - i - 1][n - j - 1]) for i in range(n)]) for j in range(n)])
r[270] = r[90]
for a0 in range(q):
	angle = int(input().strip())
	print(r[angle % 360])


import sys

def hackonacci(n):
	seq = [1, 0, 1, 0, 0, 1, 1]
	return seq[(n - 1) % 7]

def matching(n, angle, x, y):
	temp = 0
	for i in range(1, y + 1):
		for j in range(1, x + 1):
			old = hackonacci((i * j) ** 2)
			if angle == 0:
				pair = (i, j)
			elif angle == 90:
				pair = (n - j + 1, i)
			elif angle == 180:
				pair = (n - i + 1, n - j + 1)
			elif angle == 270:
				pair = (j, n - i + 1)
			new = hackonacci((pair[0] * pair[1]) ** 2)
			if old != new:
				temp += 1
	return temp
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
for a0 in range(q):
	angle = int(input().strip())
	angle = angle // 90 % 4 * 90
	count = 0
	a = n // 7
	if a >= 1:
		count += matching(n, angle, 7, 7) * a * a
	if a >= 1 and n % 7 != 0:
		count += matching(n, angle, n % 7, 7) * a
		count += matching(n, angle, 7, n % 7) * a
	if n % 7 != 0:
		count += matching(n, angle, n % 7, n % 7)
	print(count)


import sys
xx = [1, 1, 1, 0, 1, 0, 0]

def gm(size):
	x = [[0 for col in range(size)] for row in range(size)]
	for i in range(size):
		for j in range(size):
			n = ((i + 1) * (j + 1)) ** 2
			if n > 5:
				n = xx[(n - 6) % 7]
			x[i][j] = 'X' if n % 2 == 0 else 'Y'
	return x

def rotated90(arr, i, j, l):
	return arr[l - 1 - j][i]

def rotated180(arr, i, j, l):
	return arr[l - 1 - i][l - 1 - j]

def rotated270(arr, i, j, l):
	return arr[j][l - 1 - i]
results = {}

def count(arr, degree):
	result = 0
	l = len(arr)
	if degree % 360 == 0:
		return 0
	elif (degree - 270) % 360 == 0:
		key = 270
		func = rotated270
	elif (degree - 180) % 360 == 0:
		key = 180
		func = rotated180
	else:
		key = 90
		func = rotated90
	if key in results:
		return results[key]
	for i in range(l):
		for j in range(l):
			args = (arr, i, j, l)
			if arr[i][j] != func(*args):
				result += 1
	results[key] = result
	return result
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
matrix = gm(n)
for a0 in range(q):
	angle = int(input().strip())
	print(count(matrix, angle))


def get_char(n):
	l = ['X', 'Y', 'X', 'X', 'Y', 'Y', 'Y']
	return l[n % 7 - 2] if n != 1 else 'Y'

def get_diff_case(angle):
	return angle % 360 // 90

def calc_diff(mx1, mx2, n):
	count = 0
	for i in range(n):
		for j in range(n):
			if mx1[i][j] != mx2[i][j]:
				count += 1
	return count
(n, q) = map(int, input().split())
mx_0 = [[get_char((i * j) ** 2) for j in range(1, n + 1)] for i in range(1, n + 1)]
mx_1 = list(zip(*mx_0[::-1]))
mx_2 = list(zip(*mx_1[::-1]))
mx_3 = list(zip(*mx_2[::-1]))
diff_cases = [0, calc_diff(mx_0, mx_1, n), calc_diff(mx_0, mx_2, n), calc_diff(mx_0, mx_3, n)]
for a0 in range(q):
	angle = int(input().strip())
	print(diff_cases[get_diff_case(angle)])


import sys
import math
pattern = [[1, 0, 0, 0, 0, 1, 1], [0, 0, 1, 1, 0, 0, 1], [0, 1, 0, 0, 1, 0, 1], [0, 1, 0, 0, 1, 0, 1], [0, 0, 1, 1, 0, 0, 1], [1, 0, 0, 0, 0, 1, 1], [1, 1, 1, 1, 1, 1, 1]]

def h(i, j):
	return pattern[i % 7][j % 7]

def h_rotate(i, j, n, r):
	if r == 90:
		(i, j) = (n - j - 1, i)
	elif r == 180:
		(i, j) = (n - j - 1, n - i - 1)
	elif r == 270:
		(i, j) = (j, n - i - 1)
	return h(i, j)

def query(n, q):
	d = 0
	q = q % 360
	for i in range(0, n):
		for j in range(0, n):
			if h(i, j) != h_rotate(i, j, n, q):
				d += 1
	return d
cache = [0, -1, -1, -1]

def query_cache(n, q):
	qc = int(q / 90) % 4
	if cache[qc] < 0:
		cache[qc] = query(n, q)
	return cache[qc]
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
for a0 in range(q):
	angle = int(input().strip())
	print(query_cache(n, angle))


import sys
maxn = 2009
anotherArr = [0 for i in range(9)]
(anotherArr[1], anotherArr[2], anotherArr[3]) = (1, 0, 1)
for i in range(4, 9):
	if anotherArr[i - 1] + anotherArr[i - 3] == 1:
		anotherArr[i] = 1
	else:
		anotherArr[i] = 0
arr0 = [[0 for x in range(maxn)] for y in range(maxn)]
arr90 = [[0 for x in range(maxn)] for y in range(maxn)]
arr180 = [[0 for x in range(maxn)] for y in range(maxn)]
arr270 = [[0 for x in range(maxn)] for y in range(maxn)]

def iterationDecider(start, end):
	if start < end:
		return 1
	else:
		return -1

def initialization(arr, L, R, T, B):
	rowIterator = iterationDecider(L, R)
	colIterator = iterationDecider(T, B)
	for i in range(L, R, rowIterator):
		for j in range(T, B, colIterator):
			temp = ((i * j) ** 2 - 1) % 7
			if temp == 0:
				temp = 7
			temp += 1
			if anotherArr[temp] == 1:
				arr[i][j] = 1
			else:
				arr[i][j] = 0

def initialization_(arr, L, R, T, B):
	rowIterator = iterationDecider(L, R)
	colIterator = iterationDecider(T, B)
	(x, y) = (1, 1)
	for i in range(L, R, rowIterator):
		y = 1
		for j in range(T, B, colIterator):
			arr[x][y] = arr0[i][j]
			y += 1
		x += 1

def initialization__(arr, L, R, T, B):
	rowIterator = iterationDecider(L, R)
	colIterator = iterationDecider(T, B)
	(x, y) = (1, 1)
	for i in range(L, R, rowIterator):
		y = 1
		for j in range(T, B, colIterator):
			arr[x][y] = arr0[j][i]
			y += 1
		x += 1

def compareArr(arr1, arr2, n):
	differentCells = 0
	for i in range(1, n, 1):
		for j in range(1, n, 1):
			if arr1[i][j] == arr2[i][j]:
				differentCells += 0
			else:
				differentCells += 1
	return differentCells
solutionDict = {}
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
initialization(arr0, 1, n + 1, 1, n + 1)
initialization__(arr90, 1, n + 1, n, 0)
initialization_(arr180, n, 0, n, 0)
initialization__(arr270, n, 0, 1, n + 1)
solutionDict[0] = compareArr(arr0, arr0, n + 1)
solutionDict[90] = compareArr(arr0, arr90, n + 1)
solutionDict[180] = compareArr(arr0, arr180, n + 1)
solutionDict[270] = compareArr(arr0, arr270, n + 1)
for a0 in range(q):
	angle = int(input().strip())
	angle %= 360
	print(solutionDict[angle])


import sys, time
from itertools import *

def store_differences(matrix, matrices):
	diff = {}
	for (angle, rotated) in matrices.items():
		count = 0
		for (a, b) in zip(matrix, rotated):
			for (c, d) in zip(a, b):
				if c != d:
					count += 1
		diff[angle] = count
	return diff

def main():
	(n, q) = input().strip().split(' ')
	(n, q) = [int(n), int(q)]
	d = {0: 'Y', 1: 'Y', 2: 'X', 3: 'Y', 4: 'X', 5: 'X', 6: 'Y'}
	matrix = []
	for i in range(1, n + 1):
		t = [d[(i * j) ** 2 % 7] for j in range(1, n + 1)]
		matrix.append(t)
	rotated_90 = list(zip(*matrix[::-1]))
	rotated_180 = list(zip(*rotated_90[::-1]))
	rotated_270 = list(zip(*rotated_180[::-1]))
	matrices = {0: matrix, 90: rotated_90, 180: rotated_180, 270: rotated_270}
	diff = store_differences(matrix, matrices)
	for a0 in range(q):
		angle = int(input().strip()) % 360
		print(diff[angle])
main()


import sys

def cell_value(n):
	n %= 7
	if n == 2 or n == 4 or n == 5:
		return 1
	else:
		return 0
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
m = []
for r in range(1, n + 1):
	t = []
	for c in range(1, n + 1):
		t.append(cell_value((r * c) ** 2))
	m.append(t)
res = [0, 0, 0, 0]

def rotate_cell(r, c):
	r -= 1
	c -= 1
	new_r = r
	new_c = c
	for i in range(1, 4):
		temp = new_c
		new_c = n - new_r - 1
		new_r = temp
		if m[r][c] != m[new_r][new_c]:
			res[i] += 1
	return
for r in range(1, n + 1):
	for c in range(1, n + 1):
		rotate_cell(r, c)
for a0 in range(q):
	angle = int(input().strip())
	angle %= 360
	angle //= 90
	print(res[angle])


import sys
from itertools import chain
hackonaccis = [1, 2, 3]

def hackonacci(n):
	l = len(hackonaccis)
	if l >= n:
		return hackonaccis[n - 1]
	else:
		for i in range(n - l):
			hackonaccis.append(hackonaccis[-1] + 2 * hackonaccis[-2] + 3 * hackonaccis[-3])
		return hackonaccis[n - 1]
HACKONACCI_MOD_2_PATTERN = [1, 1, 0, 1, 0, 0, 1]
HACKONACCI_PATTERN_LENGTH = len(HACKONACCI_MOD_2_PATTERN)

def hackonacci_mod_2(n):
	return HACKONACCI_MOD_2_PATTERN[n % HACKONACCI_PATTERN_LENGTH]
HACKONACCI_SQUARED_MOD_2_PATTERN = [1, 1, 0, 0, 0, 0, 1]
HACKONACCI_SQUARED_PATTERN_LENGTH = len(HACKONACCI_MOD_2_PATTERN)

def hackonacci_squared_mod_2(n):
	return HACKONACCI_SQUARED_MOD_2_PATTERN[n % HACKONACCI_SQUARED_PATTERN_LENGTH]

def hackonacci_matrix(n):
	matrix = []
	row = None
	for i in range(1, n + 1):
		row = []
		for j in range(1, n + 1):
			row.append('X' if hackonacci_squared_mod_2(i * j) == 0 else 'Y')
		matrix.append(row)
	return matrix

def num_rotation_differences(n, angle):
	if n % 7 == 6:
		return 0
	q = n // 14
	r = n % 14
	n_r = small_num_rotation_differences(r, angle)
	n_q = small_corners_rotation_differences(r, angle)
	return n_r + n_q * q ** 2 + q * (small_num_rotation_differences(r + 14, angle) - n_q - n_r)

def small_corners_rotation_differences(r, angle):

	def el_at(i, j):
		return hackonacci_squared_mod_2((i + 1) * (j + 1))
	n = r + 14
	angle %= 360
	differences = 0
	centre = (n - 1) / 2
	if angle == 0:
		pass
	elif angle == 90:
		for i in chain(range(0, 7), range(7 + r, n)):
			for j in chain(range(0, 7), range(7 + r, n)):
				if el_at(i, j) != el_at(j, int(2 * centre) - i):
					differences += 1
	elif angle == 180:
		for i in chain(range(0, 7), range(7 + r, n)):
			for j in chain(range(0, 7), range(7 + r, n)):
				if el_at(i, j) != el_at(int(2 * centre) - i, int(2 * centre) - j):
					differences += 1
	elif angle == 270:
		for i in chain(range(0, 7), range(7 + r, n)):
			for j in chain(range(0, 7), range(7 + r, n)):
				if el_at(i, j) != el_at(int(2 * centre) - j, i):
					differences += 1
	else:
		raise ValueError('Angle must be a multiple of 90!')
	return differences

def small_num_rotation_differences(n, angle):

	def el_at(i, j):
		return hackonacci_squared_mod_2((i + 1) * (j + 1))
	angle %= 360
	differences = 0
	centre = (n - 1) / 2
	if angle == 0:
		pass
	elif angle == 90:
		for i in range(n):
			for j in range(n):
				if el_at(i, j) != el_at(j, int(2 * centre) - i):
					differences += 1
	elif angle == 180:
		for i in range(n):
			for j in range(n):
				if el_at(i, j) != el_at(int(2 * centre) - i, int(2 * centre) - j):
					differences += 1
	elif angle == 270:
		for i in range(n):
			for j in range(n):
				if el_at(i, j) != el_at(int(2 * centre) - j, i):
					differences += 1
	else:
		raise ValueError('Angle must be a multiple of 90!')
	return differences
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
for a0 in range(q):
	angle = int(input().strip())
	print(num_rotation_differences(n, angle))


import sys

def calc_diff(matr, rot):
	n = len(matr)
	count = 0
	rot_modulo = rot % 360
	if rot_modulo == 0:
		return 0
	if rot_modulo == 90:
		rotated = rot90(matr)
	if rot_modulo == 180:
		rotated = rot180(matr)
	if rot_modulo == 270:
		rotated = rot270(matr)
	for i in range(n):
		for j in range(n):
			if matr[i][j] != rotated.__next__():
				count += 1
	return count

def rot90(matr):
	max_n = len(matr) - 1
	col = max_n
	row = 0
	while True:
		yield matr[row][col]
		row += 1
		if row > max_n:
			(row, col) = (0, col - 1)

def rot180(matr):
	max_n = len(matr) - 1
	(row, col) = (max_n, max_n)
	while True:
		yield matr[row][col]
		col -= 1
		if col < 0:
			(row, col) = (row - 1, max_n)

def rot270(matr):
	max_n = len(matr) - 1
	(row, col) = (max_n, 0)
	while True:
		yield matr[row][col]
		row -= 1
		if row < 0:
			(row, col) = (max_n, col + 1)

def create_counts(parities, n):
	counts = [0, 0]

	def coord_to_val(i, j):
		value1 = (i + 1) % 7
		value2 = (j + 1) % 7
		multi = value1 * value2 % 7
		return multi ** 2 % 7
	for i in range(n // 2):
		for j in range(n // 2):
			cur_p = parities[coord_to_val(i, j)]
			cur_90 = parities[coord_to_val(i, n - j - 1)]
			cur_180 = parities[coord_to_val(n - i - 1, n - j - 1)]
			cur_270 = parities[coord_to_val(n - i - 1, j)]
			if cur_p != cur_90:
				counts[0] += 1
			if cur_p != cur_180:
				counts[1] += 2
			if cur_p != cur_270:
				counts[0] += 1
			if cur_90 != cur_180:
				counts[0] += 1
			if cur_90 != cur_270:
				counts[1] += 2
			if cur_180 != cur_270:
				counts[0] += 1
	if n % 2 == 1:
		mid = n // 2
		for i in range(n // 2):
			cur_p = (i, mid)
			cur_90 = (mid, n - i - 1)
			cur_180 = (n - i - 1, mid)
			cur_270 = (mid, i)
			cur_p = parities[coord_to_val(*cur_p)]
			cur_90 = parities[coord_to_val(*cur_90)]
			cur_180 = parities[coord_to_val(*cur_180)]
			cur_270 = parities[coord_to_val(*cur_270)]
			if cur_p != cur_90:
				counts[0] += 1
			if cur_p != cur_180:
				counts[1] += 2
			if cur_p != cur_270:
				counts[0] += 1
			if cur_90 != cur_180:
				counts[0] += 1
			if cur_90 != cur_270:
				counts[1] += 2
			if cur_180 != cur_270:
				counts[0] += 1
	return counts

def main(inp=sys.stdin):
	(n, q) = [int(x) for x in inp.readline().strip().split()]
	parities = [1, 1, 0, 1, 0, 0, 1]
	counts = create_counts(parities, n)
	for query in range(q):
		rota = int(inp.readline().strip()) % 360
		if rota == 180:
			print(counts[1])
		else:
			print(counts[0])

def main2(inp=sys.stdin):
	(n, q) = [int(x) for x in inp.readline().strip().split()]
	parities = [1, 1, 0, 1, 0, 0, 1]
	cur_mat = [[None for i in range(n)] for j in range(n)]
	for i in range(n):
		for j in range(n):
			value = (i + 1) * (j + 1)
			parity = parities[value ** 2 % 7]
			cur_mat[i][j] = parity
	answers = {0: calc_diff(cur_mat, 0), 90: calc_diff(cur_mat, 90), 180: calc_diff(cur_mat, 180), 270: calc_diff(cur_mat, 270)}
	for query in range(q):
		rota = int(inp.readline().strip()) % 360
		print(answers[rota])
main2()


import sys
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
haconacci_table = {1: 'Y', 2: 'X', 3: 'Y', 4: 'X', 5: 'X', 6: 'Y', 7: 'Y'}

def get_XY(n):
	return haconacci_table[(n - 1) % 7 + 1]

def _get_iterator(n, angle):
	if angle == 0:
		axis_i = range(1, n + 1)
		axis_j = range(1, n + 1)
	elif angle == 90:
		axis_i = range(1, n + 1)
		axis_j = range(n, 0, -1)
	elif angle == 180:
		axis_i = range(n, 0, -1)
		axis_j = range(n, 0, -1)
	elif angle == 270:
		axis_i = range(n, 0, -1)
		axis_j = range(1, n + 1)
	return (axis_i, axis_j)

def build_table(n):
	table = [[None for _ in range(n + 1)] for _ in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			table[i][j] = get_XY((i * j) ** 2)
	return table

def diff_table(t, a1, a2, n):
	diff = 0
	(iter_i1, iter_j1) = _get_iterator(n, a1)
	(iter_i2, iter_j2) = _get_iterator(n, a2)
	for (i1, i2) in zip(iter_i1, iter_i2):
		for (j1, j2) in zip(iter_j1, iter_j2):
			if t[i1][j1] != t[i2][j2]:
				diff += 1
	return diff
table = build_table(n)
diff_result = [0]
diff_result.append(diff_table(table, 0, 90, n))
diff_result.append(diff_table(table, 0, 180, n))
diff_result.append(diff_table(table, 0, 270, n))
for a0 in range(q):
	angle = int(input().strip())
	print(diff_result[angle % 360 // 90])


import sys
test = [False, True, False, True, True, False, False]

def par(n):
	return test[(n - 1) % 7]

def main(argv=sys.argv):
	(n, q) = input().strip().split(' ')
	(n, q) = [int(n), int(q)]
	mat = [[par((i + 1) * (i + 1) * (j + 1) * (j + 1)) for i in range(n)] for j in range(n)]
	mat90 = list(zip(*mat[::-1]))
	mat180 = list(zip(*mat90[::-1]))
	mat270 = list(zip(*mat))[::-1]
	ndiff90 = 0
	ndiff180 = 0
	ndiff270 = 0
	for i in range(n):
		for j in range(n):
			if mat[i][j] != mat90[i][j]:
				ndiff90 = ndiff90 + 1
			if mat[i][j] != mat180[i][j]:
				ndiff180 = ndiff180 + 1
			if mat[i][j] != mat270[i][j]:
				ndiff270 = ndiff270 + 1
	for a0 in range(q):
		angle = int(input().strip())
		angle = angle % 360
		ndiff = 0
		if angle == 0:
			ndiff = 0
		elif angle == 90:
			ndiff = ndiff90
		elif angle == 180:
			ndiff = ndiff180
		elif angle == 270:
			ndiff = ndiff270
		print(ndiff)
	return 0
sys.exit(main())


import sys
(mat_dim, q) = input().strip().split(' ')
(mat_dim, q) = [int(mat_dim), int(q)]
x_y_pattern = {0: 'Y', 1: 'Y', 2: 'X', 3: 'Y', 4: 'X', 5: 'X', 6: 'Y'}
hack_table = []
for row in range(1, mat_dim + 1):
	current_row = []
	for col in range(1, mat_dim + 1):
		current_row.append(x_y_pattern[(row * col) ** 2 % 7])
	hack_table.append(current_row)
rotation_pattern = {}
changed = 0
for row in range(mat_dim):
	changed += sum([el1 != el2 for (el1, el2) in zip(hack_table[row], hack_table[:][row][::-1])])
rotation_pattern[90] = changed
changed = 0
for row in range(mat_dim):
	changed += sum([el1 != el2 for (el1, el2) in zip(hack_table[row], hack_table[mat_dim - row - 1][::-1])])
rotation_pattern[180] = changed
changed = 0
for row in range(mat_dim):
	changed += sum([el1 != el2 for (el1, el2) in zip(hack_table[row], hack_table[:][mat_dim - row - 1])])
rotation_pattern[270] = changed
rotation_pattern[0] = 0
for angle in range(q):
	angle = int(input().strip())
	angle = angle % 360
	print(rotation_pattern[angle])


(n, q) = [int(x) for x in input().split()]
h = ['y', 'y', 'n', 'y', 'n', 'n', 'y']
(r90, r180) = (0, 0)
for i in range(1, 1 + n):
	ii = i * i
	i2 = n + 1 - i
	ii2 = i2 * i2 % 7
	for j in range(1, 1 + n):
		j2 = n + 1 - j
		val = h[ii * j * j % 7]
		if val != h[ii2 * j * j % 7]:
			r90 += 1
		if val != h[ii2 * j2 * j2 % 7]:
			r180 += 1
answers = [0] * 300
answers[90] = r90
answers[180] = r180
answers[270] = r90
for _ in range(q):
	print(answers[int(input()) % 360])


import sys
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
a = [0, 0, 1, 0, 1, 1, 0]
c = 0
for i in range(n):
	for j in range(n):
		t1 = ((i + 1) * (j + 1)) ** 2 % 7
		t2 = ((j + 1) * (n - (i + 1) + 1)) ** 2 % 7
		if a[t1] != a[t2]:
			c = c + 1
b = []
b.append(0)
b.append(c)
d = c
c = 0
for i in range(n):
	for j in range(n):
		t1 = ((i + 1) * (j + 1)) ** 2 % 7
		t2 = ((n - i) * (n - (j + 1) + 1)) ** 2 % 7
		if a[t1] != a[t2]:
			c = c + 1
b.append(c)
b.append(d)
for a0 in range(q):
	angle = int(input().strip())
	angle = angle % 360
	c = int(angle / 90)
	print(b[c])


hack = [1, 0, 0, 1, 1, 1, 0]

def h(n):
	if n == 1:
		return 1
	if n == 2:
		return 0
	return hack[(n - 3) % 7]

def rotate90(n):
	c = 0
	for i in range(1, n + 1):
		for j in range(1, n // 2 + 1):
			if h((i * j) ** 2) != h((i * (n + 1 - j)) ** 2):
				c += 2
	return c

def rotate270(n):
	c = 0
	for j in range(1, n + 1):
		for i in range(1, n // 2 + 1):
			if h((i * j) ** 2) != h((j * (n + 1 - i)) ** 2):
				c += 2
	return c

def rotate180(n):
	c = 0
	if n % 2 == 1:
		for i in range(1, n + 1):
			if i == n // 2 + 1:
				for j in range(1, n // 2 + 1):
					if h((i * j) ** 2) != h(((n + 1 - j) * i) ** 2):
						c += 2
				continue
			for j in range(1, n // 2 + 1):
				if h((i * j) ** 2) != h(((n + 1 - j) * (n + 1 - i)) ** 2):
					c += 2
			j = n // 2 + 1
			if h((i * j) ** 2) != h((j * (n + 1 - i)) ** 2):
				c += 1
	else:
		for i in range(1, n + 1):
			for j in range(1, n // 2 + 1):
				if h((i * j) ** 2) != h(((n + 1 - j) * (n + 1 - i)) ** 2):
					c += 2
	return c
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
d = {}
d[0] = 0
d[90] = rotate90(n)
d[180] = rotate180(n)
d[270] = rotate270(n)
for _ in range(q):
	angle = int(input().strip())
	angle %= 360
	print(d[angle])


import math

def calc_180(n):
	initial = [0, 0, 1, 3, 3, 7, 0, 15, 16, 16, 24, 27, 44, 0]
	pattern = [15, 12, 11, 11, 12, 15]
	n += 1
	f = int(n % 7)
	if f == 0:
		return 0
	f -= 1
	m = math.floor(n / 7)
	if m < 2:
		return initial[7 * m + f] * 2
	total = m * (initial[f + 7] - initial[f] + (m - 1) * pattern[f]) + initial[f]
	return int(total * 2)

def calc_90(n):
	initial = [0, 0, 1, 2, 5, 7, 0]
	pattern = [5, 2, 6, 2, 5, 4]
	n += 1
	f = int(n % 7)
	if f == 0:
		return 0
	m = math.floor(n / 7)
	if m < 1:
		return initial[f - 1] * 2
	total = m * (initial[-2] + sum(pattern) * (m - 1) / 2)
	for i in range(f):
		total += initial[i] - initial[i - 1] + m * pattern[i]
	return int(total * 2)
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
for a0 in range(q):
	angle = int(input().strip())
	angle = angle % 360
	if angle == 0:
		print(0)
	elif angle == 180:
		print(calc_180(n))
	else:
		print(calc_90(n))


import sys

def par_hacko(n):
	pattern = [1, 0, 1, 0, 0, 1, 1]
	l = len(pattern)
	return pattern[n % l - 1]

def hack_M(n):
	M = [[par_hacko((i * j) ** 2) for j in range(1, n + 1)] for i in range(1, n + 1)]
	return M

def diff(M, r):
	n = len(M)
	if r == 1 or r == 3:
		return sum([sum([1 if M[n - j - 1][i] != M[i][j] else 0 for j in range(n)]) for i in range(n)])
	elif r == 2:
		return sum([sum([1 if M[n - i - 1][n - j - 1] != M[i][j] else 0 for j in range(n)]) for i in range(n)])

def answer(n, Q):
	M = hack_M(n)
	diffs = [0, diff(M, 1), diff(M, 2), diff(M, 3)]
	Q = [q // 90 % 4 for q in Q]
	return [diffs[q] for q in Q]
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
Q = []
for a0 in range(q):
	angle = int(input().strip())
	Q.append(angle)
A = answer(n, Q)
for a in A:
	print(a)


import sys

def hackonacci(n):
	if n <= 3:
		return n
	if n in hack:
		return hack[n]
	h = (hackonacci(n - 1) + hackonacci(n - 3)) % 2
	if n < 10 ** 4:
		hack[n] = h
	return h
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
hack = {}
arr = []
for _ in range(n):
	arr.append(['Y'] * n)
for i in range(n):
	for j in range(n):
		if ((i + 1) * (j + 1)) ** 2 == 2 or (((i + 1) * (j + 1)) ** 2 - 2) % 7 in [0, 3, 2]:
			arr[i][j] = 'X'
soln = {}
for a0 in range(q):
	angle = int(input().strip())
	rotations = angle // 90 % 4
	if rotations in soln:
		print(soln[rotations])
	else:
		rotate = []
		for i in range(n):
			rotate.append(arr[i][:])
		for i in range(rotations):
			rotate = list(zip(*rotate[::-1]))
		changes = 0
		for i in range(n):
			for j in range(n):
				if rotate[i][j] != arr[i][j]:
					changes += 1
		print(changes)
		soln[rotations] = changes


import sys

def rotate_matrix_indexes(matrix):
	n = len(matrix)
	new_matrix = [[matrix[rotate_indexes(row, col, n, times=3)[0]][rotate_indexes(row, col, n, times=3)[1]] for col in range(n)] for row in range(n)]
	return new_matrix

def rotate_indexes(i, j, n, times=1):
	for time in range(times):
		z = n - j - 1
		w = i
		i = z
		j = w
	return (i, j)

def hackonacci(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	hack = [0, 1, 0, 0, 1, 1, 1]
	pos = (n - 2) % 7
	return hack[pos]

def create_matrix(n):
	matrix = [[hackonacci(((col + 1) * (row + 1)) ** 2) % 2 * 'Y' + (1 - hackonacci(((col + 1) * (row + 1)) ** 2) % 2) * 'X' for col in range(n)] for row in range(n)]
	return matrix

def rotate_matrix(matrix, times):
	if not times:
		return matrix
	new_matrix = list(zip(*matrix[::-1]))
	for rotation in range(times - 1):
		new_matrix = list(zip(*new_matrix[::-1]))
	return new_matrix

def count_differences(matrix1, matrix2):
	n = len(matrix1)
	differences = 0
	for row in range(n):
		for col in range(n):
			if matrix1[row][col] != matrix2[row][col]:
				differences += 1
	return differences
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
matrix = create_matrix(n)
cached = {}
for a0 in range(q):
	angle = int(input().strip())
	times = angle % 360 // 90
	if times:
		if times == 3:
			times = 1
		try:
			print(cached[times])
		except KeyError:
			nm = rotate_matrix(matrix, times)
			differences = count_differences(matrix, nm)
			cached[times] = differences
			print(differences)
	else:
		print(0)


[n, q] = [int(x) for x in input().split()]
query = []
for i in range(0, q):
	query.append(int(input()))
query = [int(x / 90) % 4 for x in query]
rot = [0, 0, 0]
rot_flag = [1, 0, 0]
H = [0, 1, 0, 1, 1, 0, 0]
A = []
for i in range(0, n):
	B = []
	for j in range(0, n):
		B.append(H[(((i + 1) * (j + 1)) ** 2 - 1) % 7])
	A.append(B)

def r90():
	rot_flag[1] = 1
	r = 0
	for l in range(0, n):
		for m in range(0, n):
			if A[l][m] != A[n - m - 1][l]:
				r += 1
	rot[1] = r

def r180():
	rot_flag[2] = 1
	s = 0
	for l in range(0, n):
		for m in range(0, n):
			if A[l][m] != A[n - l - 1][n - m - 1]:
				s += 1
	rot[2] = s
for i in range(0, q):
	if query[i] == 0:
		print(rot[0])
	elif query[i] == 2:
		if rot_flag[2] == 0:
			r180()
		print(rot[2])
	else:
		if rot_flag[1] == 0:
			r90()
		print(rot[1])


def rotate(m, d):
	for __ in range(d):
		m = list(zip(*m[::-1]))
	return m

def difference(x, y):
	return sum([sum([x ^ y for (x, y) in zip(i, j)]) for (i, j) in zip(x, y)])

def gethackonacci():
	h = [1, 2, 3]
	for i in range(3, 21):
		h.append(h[i - 1] + 2 * h[i - 2] + 3 * h[i - 3])
	return [(0, 1)[i % 2 == 0] for i in h]

def getmatrix(n):
	return [[h[(i * j) ** 2 % 21 - 1] for i in range(1, n + 1)] for j in range(1, n + 1)]

def solve(n, q):
	m = getmatrix(n)
	rot = []
	for __ in range(q):
		rot.append(int(input()) // 90)
	four_rotations = []
	for i in range(1, 4):
		four_rotations.append(difference(m, rotate(m, i)))
	four_rotations.append(0)
	res = [str(four_rotations[r % 4 - 1]) for r in rot]
	print('\n'.join(res))
(n, q) = map(int, input().split())
h = gethackonacci()
solve(n, q)


(n, t) = input().split()
(n, t) = (int(n), int(t))
q = []
for i in range(t):
	q.append(int(input()))
ans = [2]
x = 1
l = 1
while l <= 4000000:
	if x == 1:
		ans.append(1)
		ans.append(1)
		ans.append(1)
		ans.append(1)
		x = 0
		l = l + 4
	else:
		ans.append(2)
		ans.append(2)
		ans.append(2)
		x = 1
		l = l + 3
rotations = [0, 0, 0, 0]
a = []
b = []
for i in range(n):
	a.append([])
	for j in range(n):
		c = int(i + 1)
		d = int(j + 1)
		g = int(c * d)
		a[i].append(ans[g - 1])
b = zip(*a[::-1])
b = list(b)
count = 0
for i in range(n):
	for j in range(n):
		if a[i][j] != b[i][j]:
			count = count + 1
rotations[1] = count
b = zip(*b[::-1])
b = list(b)
count = 0
for i in range(n):
	for j in range(n):
		if a[i][j] != b[i][j]:
			count = count + 1
rotations[2] = count
b = zip(*b[::-1])
b = list(b)
count = 0
for i in range(n):
	for j in range(n):
		if a[i][j] != b[i][j]:
			count = count + 1
rotations[3] = count
for i in range(t):
	x = int(q[i] / 90 % 4)
	print(rotations[x])


import sys

def hackonacci_num(n):
	lookup = (n - 3) % 7
	hack_nums = {0: 1, 1: 1, 2: 0, 3: 1, 4: 0, 5: 0, 6: 1}
	ans = hack_nums[lookup]
	return ans

def hackonacci_mat(n):
	mat = []
	for i in range(n):
		mat.append([])
		for j in range(n):
			mat[i].append(0)
	for i in range(n):
		for j in range(i, n):
			hack_num = hackonacci_num((i + 1) * (j + 1) * (i + 1) * (j + 1))
			mat[i][j] = hack_num
			mat[j][i] = hack_num
	return mat

def mat_diff(mat, angle):
	diff_sum = 0
	for i in range(len(mat)):
		for j in range(len(mat)):
			if angle == 180:
				diff_sum += abs(mat[i][j] - mat[-i - 1][-j - 1])
			elif angle == 90:
				diff_sum += abs(mat[i][j] - mat[j][-i - 1])
			elif angle == 270:
				diff_sum += abs(mat[i][j] - mat[-j - 1][i])
	return diff_sum
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
test_mat = hackonacci_mat(n)
calc_angles = {}
for a0 in range(q):
	angle = int(input().strip())
	angle = angle % 360
	if angle in calc_angles:
		print(calc_angles[angle])
	else:
		ans = mat_diff(test_mat, angle)
		print(ans)
		calc_angles[angle] = ans


import sys

def hackonacci(int1):
	dic = {}
	(h1, h2, h3) = (1, 2, 3)
	if int1 == 1:
		dic[int1] = h1
		return dic
	elif int1 == 2:
		dic[1] = 1
		dic[int1] = h2
		return dic
	elif int1 == 3:
		(dic[1], dic[2]) = (1, 2)
		dic[int1] = h3
		return dic
	(dic[1], dic[2], dic[3]) = (1, 2, 3)
	for i in range(4, int1 + 1):
		h = (h1 + 2 * h2 + 3 * h3) % 10
		dic[i] = h
		(h1, h2, h3) = (h2, h3, h)
	return dic

def difference(mlst, n, int2):
	if int2 == 1:
		count = 0
		for i in range(n):
			for j in range(n):
				if mlst[i][j] != mlst[n - j - 1][i]:
					count += 1
		return count
	elif int2 == 2:
		count = 0
		for i in range(n):
			for j in range(n):
				if mlst[i][j] != mlst[n - i - 1][n - j - 1]:
					count += 1
		return count
	else:
		count = 0
		for i in range(n):
			for j in range(n):
				if mlst[i][j] != mlst[j][n - i - 1]:
					count += 1
		return count
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
mtx = []
for i in range(n):
	mtx.append(list('O' * n))
hack_dic = hackonacci(n * n)
for i in range(1, n + 1):
	for j in range(i, n + 1):
		if (i * j - 3) % 7 == 0:
			rem = (hack_dic[i * j] + 1) % 2
		else:
			rem = hack_dic[i * j] % 2
		c = 'X' if rem == 0 else 'Y'
		if i != j:
			mtx[j - 1][i - 1] = c
		mtx[i - 1][j - 1] = c
dic_q = {0: 0, 1: difference(mtx, n, 1), 2: difference(mtx, n, 2), 3: difference(mtx, n, 3)}
for a0 in range(q):
	angle = int(input().strip())
	k = angle // 90 % 4
	print(dic_q[k])


import math

def rotate(X):
	l = [[X[j][i] for j in range(len(X) - 1, -1, -1)] for i in range(0, len(X))]
	return l

def ro(l):
	A = rotate(l)
	B = rotate(A)
	C = rotate(B)
	t90 = 0
	t180 = 0
	t270 = 0
	for i in range(n):
		for j in range(n):
			if A[i][j] != l[i][j]:
				t90 += 1
			if B[i][j] != l[i][j]:
				t180 += 1
			if C[i][j] != l[i][j]:
				t270 += 1
	return (t90, t180)
l = ['X    X', '  XX  ', ' X  X ', ' X  X ', '  XX  ', 'X    X']
t = list(l)
(n, k) = [int(x) for x in input().split()]
(r, c) = (6, 6)
if n > 6:
	while c < n:
		if c + 7 < n:
			for i in range(6):
				l[i] = l[i] + 'X' + t[i]
			c += 7
		else:
			for i in range(6):
				l[i] = l[i] + 'X' + t[i][0:n - c - 1]
			c = n
	while r < n:
		l.append('X' * c)
		if r + 7 < n:
			for i in range(6):
				l.append(l[i])
		else:
			for i in range(n - r - 1):
				l.append(l[i])
		r += 7
else:
	t = t[:n]
	for i in range(len(t)):
		t[i] = t[i][:n]
	l = t
(t9, t18) = ro(l)
for i in range(k):
	x = int(input()) % 360
	if x == 0:
		print('0')
	elif x == 90 or x == 270:
		print(t9)
	else:
		print(t18)


import sys
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
v = [False, True, False, True, True, False, False]
g = []
for i in range(n):
	g.append([])
	for o in range(n):
		g[i].append(-1)

def gp(i, o):
	if g[i][o] == -1:
		g[i][o] = v[((i + 1) * (o + 1) * ((i + 1) * (o + 1)) - 1) % len(v)]
	return g[i][o]
angle90 = -1
angle180 = -1
angle270 = -1
for a0 in range(q):
	angle = int(input().strip())
	diff = 0
	angle = angle % 360
	if angle == 90:
		if angle90 == -1:
			for i in range(n):
				for o in range(n):
					if gp(i, o) != gp(n - i - 1, o):
						diff += 1
			angle90 = diff
		else:
			diff = angle90
	elif angle == 180:
		if angle180 == -1:
			for i in range(n):
				for o in range(n):
					if gp(i, o) != gp(n - i - 1, n - o - 1):
						diff += 1
			angle180 = diff
		else:
			diff = angle180
	elif angle == 270:
		if angle270 == -1:
			for i in range(n):
				for o in range(n):
					if gp(i, o) != gp(i, n - o - 1):
						diff += 1
			angle270 = diff
		else:
			diff = angle270
	print(diff)


(n, q) = map(int, input().split())
m = [[i * i * j * j % 7 in [1, 3, 6, 0] for j in range(1, n + 1)] for i in range(1, n + 1)]
(r, mr) = ([0], list(m))
for _ in range(3):
	mr = list(zip(*mr))[::-1]
	r.append(sum((m[i][j] != mr[i][j] for i in range(n) for j in range(n))))
for _ in range(q):
	angle = int(input().strip())
	print(r[angle // 90 % 4])


import sys

def hackonacci(d):
	if d == 1:
		return 1
	if d == 2:
		return 0
	if d == 3:
		return 1
	h = [0, 0, 1, 1, 1, 0, 1]
	return h[(d - 4) % len(h)]
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]

def rotated_diffs(s):
	diffs = [0, 0, 0, 0]
	for col in range(1, s // 2 + 1):
		for row in range(1, s + 1):
			left = hackonacci(pow(row * col, 2))
			right_reflect = hackonacci(pow(row * (s - col + 1), 2))
			diffs[1] += int(left != right_reflect) * 2
	for row in range(1, s + 1):
		for col in range(1, s - row + 1):
			top_left = hackonacci(pow(row * col, 2))
			bottom_right_reflect = hackonacci(pow((s - row + 1) * (s - col + 1), 2))
			diffs[2] += int(top_left != bottom_right_reflect) * 2
	diffs[3] = diffs[1]
	return diffs
diffs_ = rotated_diffs(n)
for a0 in range(q):
	angle = int(input().strip()) % 360
	print(diffs_[angle // 90])


import sys
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
vlist = [1, 0, 1, 0, 0, 1, 1]
arr = [[vlist[(i * j) ** 2 % 7 - 1] for i in range(1, n + 1)] for j in range(1, n + 1)]
result = {}
for a0 in range(q):
	angle = int(input().strip())
	(tot, angle) = (0, angle % 360)
	if angle not in result:
		if angle == 90:
			res = list(zip(*arr[::-1]))
		elif angle == 180:
			res = [row[::-1] for row in arr[::-1]]
		elif angle == 270:
			res = list(zip(*arr[::-1]))
			res = [row[::-1] for row in res[::-1]]
		else:
			res = arr
		result[angle] = sum([1 for i in range(n) for j in range(n) if res[i][j] != arr[i][j]])
	tot = result[angle]
	print(tot)


import sys
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
angle = [int(input().strip()) for a0 in range(q)]
sq = [i * i for i in range(0, n + 1)]
M = []
for i in range(1, n + 1):
	L = n * [False]
	for j in range(1, n + 1):
		L[j - 1] = 1 if sq[i] * sq[j] % 7 in [0, 1, 3, 6] else 0
	M.append(L)
cnt = [0, 0, 0, 0]
N = n - 1
for i in range(0, n):
	for j in range(0, n):
		cnt[3] += 0 if M[i][j] == M[j][N - i] else 1
		cnt[2] += 0 if M[i][j] == M[N - i][N - j] else 1
		cnt[1] += 0 if M[i][j] == M[N - j][i] else 1
for i in range(q):
	angle[i] = angle[i] % 360 // 90
	print(cnt[angle[i]])


import sys

def rotate(n, mat_arg):
	mat = [[item for item in row] for row in mat_arg]
	for i in range(n // 2):
		for j in range(i, n - i - 1):
			tmp = mat[i][j]
			mat[i][j] = mat[n - j - 1][i]
			mat[n - j - 1][i] = mat[n - i - 1][n - j - 1]
			mat[n - i - 1][n - j - 1] = mat[j][n - i - 1]
			mat[j][n - i - 1] = tmp
	return mat

def guess(hack, i, j):
	idx = ((i + 1) * (j + 1)) ** 2 % 56
	return 'Y' if hack[idx - 1] & 1 > 0 else 'X'

def get_diff(mat1, mat2):
	cnt = 0
	for i in range(len(mat1)):
		for j in range(len(mat1[0])):
			if mat1[i][j] != mat2[i][j]:
				cnt += 1
	return cnt
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
hack = [0] * 1000
hack[1] = 1
hack[2] = 2
hack[3] = 3
for i in range(4, 1000):
	hack[i] = (hack[i - 1] + 2 * hack[i - 2] + 3 * hack[i - 3]) % 10
hack = hack[1:57]
mat = [[guess(hack, i, j) for j in range(n)] for i in range(n)]
mats = []
mats.append(mat)
temp = mat
for i in range(3):
	temp = rotate(n, temp)
	mats.append(temp)
diffs = [0, get_diff(mats[0], mats[1]), get_diff(mats[0], mats[2]), get_diff(mats[0], mats[3])]
for a0 in range(q):
	angle = int(input().strip()) // 90 % 4
	print(diffs[angle])


import sys

def changesCount(matrix, degree):
	count = 0
	if degree == 90:
		for x in range(len(matrix)):
			for i in range(len(matrix)):
				if matrix[x][i] != matrix[len(matrix) - 1 - i][x]:
					count += 1
	elif degree == 180:
		for x in range(len(matrix)):
			for i in range(len(matrix)):
				if matrix[x][i] != matrix[len(matrix) - 1 - x][len(matrix) - 1 - i]:
					count += 1
	elif degree == 270:
		for x in range(len(matrix)):
			for i in range(len(matrix)):
				if matrix[x][i] != matrix[i][len(matrix) - 1 - x]:
					count += 1
	return count
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
matrix = [[] for x in range(n)]
counts = [[-1] for x in range(3)]
for i in range(0, n):
	for x in range(0, n):
		num = ((i + 1) * (x + 1)) ** 2
		num = num % 7
		if num == 2 or num == 4 or num == 5:
			matrix[i].append('X')
		else:
			matrix[i].append('Y')
for a in range(q):
	angle = int(input().strip())
	degree = angle % 360
	if degree == 90 and counts[0][0] == -1:
		counts[0][0] = changesCount(matrix, degree)
		print(counts[0][0])
	elif degree == 90 and counts[0][0] != -1:
		print(counts[0][0])
	if degree == 180 and counts[1][0] == -1:
		counts[1][0] = changesCount(matrix, degree)
		print(counts[1][0])
	elif degree == 180 and counts[1][0] != -1:
		print(counts[1][0])
	if degree == 270 and counts[2][0] == -1:
		counts[2][0] = changesCount(matrix, degree)
		print(counts[2][0])
	elif degree == 270 and counts[2][0] != -1:
		print(counts[2][0])
	if degree == 0:
		print(0)


import sys
import math
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
angle = []
d = dict()
d[0] = 0
d[90] = None
d[180] = None
d[270] = None
for a0 in range(q):
	angle.append(int(input().strip()))
a = [0, 1, 6, 8, 15, 20, 36]
Matrix = [[0 for x in range(n)] for y in range(n)]
for i in range(n):
	for j in range(n):
		x = (j + 1) % 7 * ((i + 1) % 7)
		if x in a:
			Matrix[j][i] = 1
for c in angle:
	if d[c % 360] == None:
		d[c % 360] = 0
		if c % 360 == 90:
			for i in range(n):
				for j in range(n):
					if Matrix[i][j] ^ Matrix[n - j - 1][i]:
						d[90] = d[90] + 1
			print(d[90])
		if c % 360 == 180:
			for i in range(n):
				for j in range(n):
					if Matrix[i][j] ^ Matrix[n - i - 1][n - j - 1]:
						d[180] = d[180] + 1
			print(d[180])
		if c % 360 == 270:
			for i in range(n):
				for j in range(n):
					if Matrix[i][j] ^ Matrix[j][n - i - 1]:
						d[270] = d[270] + 1
			print(d[270])
	else:
		print(d[c % 360])


import sys
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]

def f(i, j):
	return [1, 1, 0, 1, 0, 0, 1][(i * j) ** 2 % 7]
(ans90, ans180) = (0, 0)
for i in range(1, n // 2 + 1):
	for j in range(1, (n + 1) // 2 + 1):
		a = [f(i, j), f(n + 1 - j, i), f(n + 1 - i, n + 1 - j), f(j, n + 1 - i)]
		ans90 += abs(a[0] - a[1]) + abs(a[1] - a[2]) + abs(a[2] - a[3]) + abs(a[3] - a[0])
		ans180 += abs(a[0] - a[2]) * 2 + abs(a[1] - a[3]) * 2
for a0 in range(q):
	angle = int(input().strip())
	print([0, ans90, ans180, ans90][angle % 360 // 90])


def hl(n):
	return 'YYXYXXY'[n % 7]

def f(n):
	quarter = 0
	half = 0
	for i in range(1, 1 + n):
		for j in range(1, 1 + n):
			(i1, j1) = (j, n + 1 - i)
			(i2, j2) = (n + 1 - i, n + 1 - j)
			this_letter = hl((i * j) ** 2)
			quarter_letter = hl((i1 * j1) ** 2)
			half_letter = hl((i2 * j2) ** 2)
			quarter += this_letter != quarter_letter
			half += this_letter != half_letter
	return (quarter, half)
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
(qu, ha) = f(n)
for a0 in range(q):
	angle = int(input().strip())
	if angle % 360 == 0:
		print(0)
	elif angle % 180 == 0:
		print(ha)
	else:
		print(qu)


import sys
hack = [False, False, True, False, True, True, False]
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
X = [['X' if hack[((i + 1) * (j + 1)) ** 2 % 7] else 'Y' for j in range(n)] for i in range(n)]

def not_equals_new_pos(i, j, m):
	if m % 4 == 0:
		return False
	if m % 4 == 1:
		return X[i][j] != X[i][n - j - 1]
	if m % 4 == 2:
		return X[i][j] != X[n - i - 1][n - j - 1]
	if m % 4 == 3:
		return X[i][j] != X[n - i - 1][j]
D = {m: sum((not_equals_new_pos(i, j, m) for i in range(n) for j in range(n))) for m in range(4)}
for a0 in range(q):
	print(D[int(input().strip()) // 90 % 4])


import sys
pattern = [1, 0, 1, 0, 0, 1, 1]
matrix = []
n = 0

def prep_matrix():
	for i in range(n):
		matrix.append([False] * n)
	for i in range(n):
		for j in range(n):
			k = (i + 1) * (j + 1)
			k *= k
			matrix[i][j] = pattern[(k - 1) % len(pattern)]

def count90():
	result = 0
	for i in range(n):
		for j in range(n):
			if matrix[i][j] != matrix[n - j - 1][i]:
				result += 1
	return result

def count180():
	result = 0
	for i in range(n):
		for j in range(n):
			if matrix[i][j] != matrix[n - i - 1][n - j - 1]:
				result += 1
	return result

def count270():
	result = 0
	for i in range(n):
		for j in range(n):
			if matrix[i][j] != matrix[j][n - i - 1]:
				result += 1
	return result
(n, q) = map(int, input().strip().split())
prep_matrix()
result = {}
result[0] = 0
result[90] = count90()
result[180] = count180()
result[270] = count270()
for a0 in range(q):
	angle = int(input().strip()) % 360
	print(result[angle])


import sys
h_all = [None, 'X', 'Y', 'X', 'Y', 'Y', 'X', 'X', 'X']

def h(n):
	if n > 8:
		n = (n - 1) % 7
		n += 1
	return h_all[n]
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
results = [0, None, None, None]
for a0 in range(q):
	angle = int(input().strip())
	angle = angle % 360
	z = int(angle / 90)
	if results[z] != None:
		print(results[z])
	else:
		total = 0
		if z == 2:
			for i in range(1, n + 1):
				for j in range(1, i + 1):
					ir = n - (i - 1)
					jr = n - (j - 1)
					if h((i * j) ** 2) != h((ir * jr) ** 2):
						if i == j:
							total += 1
						else:
							total += 2
			results[z] = total
		else:
			jrange = n // 2
			g = None
			if n % 2:
				jrange += 1
				g = jrange
			for i in range(1, n + 1):
				for j in range(1, jrange + 1):
					ir = n - j + 1
					jr = i
					if h((i * j) ** 2) != h((ir * jr) ** 2):
						if j == g:
							total += 1
						else:
							total += 2
			results[1] = results[3] = total
		print(total)


import sys

def set_value(n):
	if n % 7 in (1, 3, 6, 0):
		return 'Y'
	else:
		return 'X'

def rotate_90(matrice):
	for i in range(n):
		for j in range(n):
			r_matrice[i][j] = matrice[n - 1 - j][i]
	return r_matrice

def rotate_180(matrice):
	for i in range(n):
		for j in range(n):
			r_matrice[i][j] = matrice[n - 1 - i][n - 1 - j]
	return r_matrice

def rotate_270(matrice):
	for i in range(n):
		for j in range(n):
			r_matrice[i][j] = matrice[j][n - 1 - i]
	return r_matrice

def compare(m1, m2):
	diff = 0
	for i in range(n):
		for j in range(n):
			if m1[i][j] != m2[i][j]:
				diff += 1
	return diff
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
matrice = [['Z' for _ in range(n)] for _ in range(n)]
r_matrice = [['Z' for _ in range(n)] for _ in range(n)]
for i in range(n):
	for j in range(n):
		matrice[i][j] = set_value(((i + 1) * (j + 1)) ** 2)
diff_90 = compare(matrice, rotate_90(matrice))
diff_180 = compare(matrice, rotate_180(matrice))
diff_270 = compare(matrice, rotate_270(matrice))
for a0 in range(q):
	angle = int(input().strip()) % 360
	if angle == 90:
		print(diff_90)
	elif angle == 180:
		print(diff_180)
	elif angle == 270:
		print(diff_270)
	else:
		print('0')


import sys
hackonnaci_dict = dict({0: 'Y', 1: 'X', 2: 'Y', 3: 'X', 4: 'X', 5: 'Y', 6: 'Y'})

def hackonnaci(x):
	return hackonnaci_dict[(x - 1) % 7]

def num_matrix_diffs(a, b):
	num_diffs = 0
	for i in range(len(a)):
		for j in range(len(b)):
			if a[i][j] != b[i][j]:
				num_diffs += 1
	return num_diffs

def rotate(matrix):
	temp_matrix = []
	for row in matrix:
		temp_matrix.append(row[::-1])
	result = []
	for tup in zip(*temp_matrix):
		result.append(list(tup))
	return result

def create_matrix(n):
	mat = []
	for i in range(1, n + 1):
		row = []
		for j in range(1, n + 1):
			row.append(hackonnaci((i * j) ** 2))
		mat.append(row)
	return mat
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
matrix0 = create_matrix(n)
matrix90 = rotate(matrix0)
matrix180 = rotate(matrix90)
matrix270 = rotate(matrix180)
diffs90 = num_matrix_diffs(matrix0, matrix90)
diffs180 = num_matrix_diffs(matrix0, matrix180)
diffs270 = num_matrix_diffs(matrix0, matrix270)
for a0 in range(q):
	angle = int(input().strip()) % 360
	if angle == 0:
		print(0)
	if angle == 90:
		print(diffs90)
	if angle == 180:
		print(diffs180)
	if angle == 270:
		print(diffs270)


import sys

def hack_odd(n):
	if n == 1:
		return 1
	else:
		return [0, 1, 0, 0, 1, 1, 1][(n - 2) % 7]

def hack_matrix(n):
	result = [[None for _ in range(n)] for _ in range(n)]
	for r in range(n):
		for c in range(n):
			if hack_odd(((r + 1) * (c + 1)) ** 2):
				result[r][c] = 'y'
			else:
				result[r][c] = 'x'
	return result

def flip(mat, n):
	return [[mat[r][n - 1 - c] for c in range(n)] for r in range(n)]

def rotate90(mat, n):
	return flip([[mat[c][r] for c in range(n)] for r in range(n)], n)
memo_rots = {}

def rotate(mat, n, angle):
	angle = round(angle % 360 / 90)
	if angle in memo_rots:
		return memo_rots[angle]
	else:
		for i in range(1, angle + 1):
			mat = rotate90(mat, n)
			if i not in memo_rots:
				memo_rots[i] = mat
		return memo_rots[angle]
memo_diffs = {}

def num_diffs(mat, n, angle):
	if angle % 360 == 0:
		return 0
	elif angle % 360 in memo_diffs:
		return memo_diffs[angle % 360]
	else:
		mat2 = rotate(mat, n, angle)
		diffs = 0
		for r in range(n):
			for c in range(n):
				if mat[r][c] != mat2[r][c]:
					diffs += 1
		memo_diffs[angle % 360] = diffs
		return diffs
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
mat = hack_matrix(n)
for a0 in range(q):
	angle = int(input().strip())
	print(num_diffs(mat, n, angle))


(n, g) = map(int, input().split())
hack = [1, 1, 0, 1, 0, 0, 1]
A = [[] for i in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, n + 1):
		if hack[i * i * j * j % 7] == 0:
			A[i].append('X')
		else:
			A[i].append('Y')
B = []
for i in range(n + 1):
	if len(A[i]) != 0:
		B.append(A[i])
rot90 = tuple(zip(*B[::-1]))
rot180 = tuple(zip(*rot90[::-1]))
rot270 = tuple(zip(*rot180[::-1]))
ans = [0, 0, 0, 0]
for i in range(n):
	for j in range(n):
		if B[i][j] != rot90[i][j]:
			ans[1] += 1
		if B[i][j] != rot180[i][j]:
			ans[2] += 1
		if B[i][j] != rot270[i][j]:
			ans[3] += 1
for k in range(g):
	q = int(input())
	if q % 360 == 0:
		a = ans[0]
	elif q % 360 == 90:
		a = ans[1]
	elif q % 360 == 180:
		a = ans[2]
	else:
		a = ans[3]
	print(a)


def solve(n, queries):
	a = [[((i + 1) * (j + 1)) ** 2 % 7 in [0, 1, 3, 6] for j in range(n)] for i in range(n)]
	b = a
	ans = []
	for i in range(4):
		diff = 0
		for i in range(n):
			for j in range(n):
				if a[i][j] != b[i][j]:
					diff += 1
		ans.append(diff)
		b = rotate(b)
	return [ans[q // 90 % 4] for q in queries]

def rotate(a):
	return [[a[j][i] for j in range(len(a))] for i in range(len(a[0]) - 1, -1, -1)]

def test():
	assert solve(4, [90, 180, 270]) == [10, 6, 10]
	solve(2000, [10 ** 5] * 10 ** 4)

def read_ints():
	return list(map(int, input().split()))
(n, q) = read_ints()
queries = [int(input()) for _ in range(q)]
print(*solve(n, queries), sep='\n')


from itertools import chain
from operator import xor
from collections import deque
from math import sqrt

def is_square(n):
	sn = sqrt(n)
	return sn - int(sn) < 1e-06

def rotate(X):
	return [[X[n - j - 1][i] for j in range(n)] for i in range(n)]

def diff(x, y):
	return sum(map(xor, chain(*x), chain(*y)))

def printm(X):
	print(*X, sep='\n', end='\n\n')
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
h = [1, 1, 0, 1, 0, 0, 1]
m = [[h[(i * j) ** 2 % 7] for j in range(1, n + 1)] for i in range(1, n + 1)]
m1 = rotate(m)
m2 = rotate(m1)
m3 = rotate(m2)
state = 0
ans = [[0 for j in range(4)] for i in range(4)]
ans[0][1] = ans[1][3] = diff(m, m1)
ans[0][2] = ans[2][2] = diff(m, m2)
ans[0][3] = ans[3][1] = diff(m, m3)
ans[1][1] = ans[2][3] = diff(m1, m2)
ans[1][2] = ans[3][2] = diff(m1, m3)
ans[2][1] = ans[3][3] = diff(m2, m3)
for a0 in range(q):
	angle = int(input().strip()) % 360 // 90
	print(ans[state][angle])
	state = (state + angle) % 4


import sys

def solve1(n, dp):
	if n == 1 or n == 2 or n == 3:
		return n
	if dp[n] != -1:
		return dp[n]
	dp[n] = 1 * solve1(n - 1, dp) + 2 * solve1(n - 2, dp) + 3 * solve1(n - 3, dp)
	return dp[n]

def solve(matrix, dp):
	for i in range(7):
		for j in range(7):
			answer = dp[((i + 1) * (j + 1)) ** 2]
			if answer % 2 == 0:
				matrix[i][j] = 'X'
			else:
				matrix[i][j] = 'Y'
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
matrix = [[0] * 7 for _ in range(7)]
dp = [-1 for _ in range((7 * 7) ** 2 + 1)]
for i in range((7 * 7) ** 2 + 1)[1:]:
	if i == 1 or i == 2 or i == 3:
		dp[i] = i
	else:
		dp[i] = (1 * dp[i - 1] + 2 * dp[i - 2] + 3 * dp[i - 3]) % 10
solve(matrix, dp)
lookup = matrix
mat = [[-1] * n for _ in range(n)]
for i in range(n):
	for j in range(n):
		if (i + 1) % 7 == 0 or (j + 1) % 7 == 0:
			mat[i][j] = 'Y'
		else:
			mat[i][j] = lookup[i % 7][j % 7]
angle1 = [-1 for i in range(3)]
for a0 in range(q):
	angle = int(input().strip())
	count = 0
	if angle % 360 == 90:
		if angle1[0] != -1:
			count = angle1[0]
		else:
			for i in range(n):
				for j in range(n):
					if mat[i][j] != mat[j][n - 1 - i]:
						count += 1
			angle1[0] = count
	if angle % 360 == 180:
		if angle1[1] != -1:
			count = angle1[1]
		else:
			for i in range(n):
				for j in range(n):
					if mat[i][j] != mat[n - 1 - i][n - 1 - j]:
						count += 1
			angle1[1] = count
	if angle % 360 == 270:
		if angle1[2] != -1:
			count = angle1[2]
		else:
			for i in range(n):
				for j in range(n):
					if mat[i][j] != mat[n - 1 - j][i]:
						count += 1
			angle1[2] = count
	print(count)


from itertools import chain
hack_pattern = (False, True, False, True, True, False, False)

def hackonacci_even(n):
	return hack_pattern[(n - 1) % 7]

def matrix_rotate_90(mat):
	return list(zip(*mat[::-1]))

def matrix_iter(mat):
	return chain.from_iterable(mat)

def matrix_differences(mat1, mat2):
	return sum((x != y for (x, y) in zip(matrix_iter(mat1), matrix_iter(mat2))))
(n, q) = [int(x) for x in input().strip().split(' ')]
matrix = [[hackonacci_even(i * i * j * j) for j in range(1, n + 1)] for i in range(1, n + 1)]
mat_differences = [0, 0, 0, 0]
rotated_matrix = matrix
for i in range(1, 4):
	rotated_matrix = matrix_rotate_90(rotated_matrix)
	mat_differences[i] = matrix_differences(matrix, rotated_matrix)
for _ in range(q):
	angle = int(input().strip())
	rotations = angle % 360 // 90
	print(mat_differences[rotations])


def hackonacci(x):
	result = (x - 2) % 7
	if result == 0 or result == 2 or result == 3:
		return 0
	else:
		return 1
(n, q) = input().strip().split(' ')
(n, q) = (int(n), int(q))
board = [None] * n
board90 = [None] * n
board180 = [None] * n
board270 = [None] * n
for i in range(n):
	board[i] = [None] * n
	board90[i] = [None] * n
	board180[i] = [None] * n
	board270[i] = [None] * n
for i in range(1, n + 1):
	for k in range(1, n + 1):
		idx = i * k * i * k
		board[i - 1][k - 1] = hackonacci(idx)
for i in range(n):
	for k in range(n):
		idx = k
		idy = n - i - 1
		board90[idx][idy] = board[i][k]
for i in range(n):
	for k in range(n):
		board180[n - i - 1][n - k - 1] = board[i][k]
for i in range(n):
	for k in range(n):
		board270[n - i - 1][n - k - 1] = board90[i][k]
diff90 = 0
diff180 = 0
diff270 = 0
for i in range(n):
	for k in range(n):
		if board90[i][k] != board[i][k]:
			diff90 += 1
		if board180[i][k] != board[i][k]:
			diff180 += 1
		if board270[i][k] != board[i][k]:
			diff270 += 1
for i in range(q):
	angle = int(input().strip())
	angle = angle % 360 / 90
	if angle == 1:
		print(diff90)
	elif angle == 2:
		print(diff180)
	elif angle == 3:
		print(diff270)
	else:
		print(0)


import sys

def h(n):
	if n in [1, 2, 3]:
		return n
	return 1 * h(n - 1) + 2 * h(n - 2) + 3 * h(n - 3)

def printm(m):
	for a in m:
		print(a)
	print('------------------')

def rotate90(m):
	(B, lenm) = ([], len(m))
	for r in range(0, lenm):
		brow = ''
		for c in range(lenm - 1, -1, -1):
			brow += m[c][r]
		B.append(brow)
	return B

def rotate180(m):
	(B, lenm) = ([], len(m))
	for r in range(0, lenm):
		brow = ''
		for c in range(lenm - 1, -1, -1):
			brow += m[lenm - r - 1][c]
		B.append(brow)
	return B

def rotate270(m):
	(B, lenm) = ([], len(m))
	for r in range(lenm - 1, -1, -1):
		brow = ''
		for c in range(0, lenm):
			brow += m[c][r]
		B.append(brow)
	return B

def m(n):
	B = ['1000011', '0011001', '0100101', '0100101', '0011001', '1000011', '1111111']
	A = []
	for r in range(1, n + 1):
		r7 = r % 7 - 1
		if r7 == -1:
			r7 = 6
		s = ''
		for c in range(1, n + 1):
			c7 = c % 7 - 1
			if c7 == -1:
				c7 = 6
			s += B[r7][c7]
		A.append(s)
	return A
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
A = m(n)
B = rotate90(A)
C = rotate180(A)
D = rotate270(A)
(tot90, tot180, tot270) = (0, 0, 0)
for r in range(0, n):
	for c in range(0, n):
		if A[r][c] != B[r][c]:
			tot90 += 1
		if A[r][c] != C[r][c]:
			tot180 += 1
		if A[r][c] != D[r][c]:
			tot270 += 1
for a0 in range(q):
	angle = int(input().strip())
	angle %= 360
	if angle == 0:
		print(0)
	elif angle == 90:
		print(tot90)
	elif angle == 180:
		print(tot180)
	else:
		print(tot270)


def hacko(n):
	p = n % 7
	if p < 2 or p == 6:
		return 1
	else:
		return 0

def r90(x, y, size):
	if hacko(x * y) == hacko(y * (size - x + 1)):
		return 0
	else:
		return 1

def r180(x, y, size):
	if hacko(x * y) == hacko((size - x + 1) * (size - y + 1)):
		return 0
	else:
		return 1
(n, q) = [int(i) for i in input().split()]
(r1, r2) = (0, 0)
out = []
for i in range(1, n + 1):
	for j in range(1, n + 1):
		r1 += r90(i, j, n)
		r2 += r180(i, j, n)
for _ in range(q):
	angle = int(input()) % 360
	if angle == 0:
		out.append('0')
	elif angle == 180:
		out.append(str(r2))
	else:
		out.append(str(r1))
print('\n'.join(out))


import sys
import time

def mtx_el(i, j):
	value_store = [1, 0, 1, 0, 0, 1, 1]
	return value_store[(i * i * j * j - 1) % 7]

def get_angle(a):
	return a % 360

def rotate_90(n):
	s = sum([1 for i in range(1, n + 1) for j in range(1, n + 1) if mtx_el(i, j) != mtx_el(n - j + 1, i)])
	return s

def rotate_180(n):
	s = sum([1 for i in range(1, n + 1) for j in range(1, n + 1) if mtx_el(i, j) != mtx_el(n - i + 1, n - j + 1)])
	return s

def rotate_270(n):
	s = sum([1 for i in range(1, n + 1) for j in range(1, n + 1) if mtx_el(i, j) != mtx_el(j, n - i + 1)])
	return s

def rotate(a, n):
	angle = get_angle(a)
	if angle == 0:
		return 0
	if angle == 90:
		return rotate_90(n)
	if angle == 180:
		return rotate_180(n)
	if angle == 270:
		return rotate_270(n)
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
rdict = {0: 0}
rdict[90] = rotate(90, n)
rdict[180] = rotate(180, n)
rdict[270] = rdict[90]
for i in range(q):
	angle = get_angle(int(input().strip()))
	print(rdict[angle])


import sys

def hacko_parity(i):
	parity = {0: 1, 1: 0, 2: 1, 3: 0, 4: 0, 5: 1, 6: 1}
	i = (i - 1) % 7
	return parity[i]
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
matrix = [[0 for c in range(n)] for r in range(n)]
for c in range(n):
	for r in range(n):
		if hacko_parity(((c + 1) * (r + 1)) ** 2):
			matrix[r][c] = 'Y'
		else:
			matrix[r][c] = 'X'
(rotate_90, rotate_180) = (0, 0)
for c in range(n):
	for r in range(n):
		if matrix[r][c] != matrix[c][n - 1 - r]:
			rotate_90 += 1
		if matrix[r][c] != matrix[n - 1 - r][n - 1 - c]:
			rotate_180 += 1
for a0 in range(q):
	angle = int(input().strip())
	angle %= 360
	if angle == 0:
		print(0)
	elif angle == 180:
		print(rotate_180)
	else:
		print(rotate_90)


import sys

def hackonacci(n):
	hn = {1: 1, 2: 2, 3: 3}

	def hcknc(n):
		if n not in hn:
			hn[n] = hcknc(n - 1) + 2 * hcknc(n - 2) + 3 * hcknc(n - 3)
		return hn[n]
	return hcknc(n)
(n, q) = [int(s) for s in input().strip().split(' ')]
nacci0 = [2, 4, 5]
mat = [[1] * n for i in range(n)]
for i in range(1, n + 1):
	for j in range(i, n + 1):
		if i * i * j * j % 7 in nacci0:
			mat[i - 1][j - 1] = 0
			mat[j - 1][i - 1] = 0
res = [0] * 4
for i in range(n):
	for j in range(n):
		res[1] += abs(mat[i][j] - mat[j][n - 1 - i])
		res[2] += abs(mat[i][j] - mat[n - 1 - i][n - 1 - j])
		res[3] += abs(mat[i][j] - mat[n - 1 - j][i])
for i in range(q):
	a = int(input().strip())
	print(res[a // 90 % 4])


def x(i, j):
	s = (i + 1) * (j + 1) % 7
	s = (s + 7) % 7
	return 1 if 2 <= s <= 5 else 0

def qry(n, a):
	if a == 0:
		return 0
	if n % 7 == 6:
		return 0
	n -= 1
	m = []
	for i in range(7):
		if a == 180:
			m.append([x(i, j) ^ x(n - i, n - j) for j in range(7)])
		elif a == 90:
			m.append([x(i, j) ^ x(n - j, i) for j in range(7)])
		elif a == 270:
			m.append([x(i, j) ^ x(j, n - i) for j in range(7)])
	(u, v) = (n // 7, n % 7)
	(n, v) = (n + 1, v + 1)
	return u * u * sum((sum(c) for c in m)) + u * sum((sum(c) for c in m[:v])) + u * sum((sum(c[:v]) for c in m)) + sum((sum(c[:v]) for c in m[:v]))
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
for a0 in range(q):
	angle = int(input().strip()) % 360
	print(qry(n, angle))


(n, q) = map(int, input().split())
angles = [int(input()) for i in range(q)]
a = [1, 1, 0, 1, 0, 0, 1]
quarter = half = 0
for i in range(1, n + 1):
	ni = n - i + 1
	ii = i * i
	nii = ni * ni
	for j in range(1, n + 1):
		if a[ii * j * j % 7] != a[nii * j * j % 7]:
			quarter += 1
		if a[ii * j * j % 7] != a[nii * (n - j + 1) ** 2 % 7]:
			half += 1
answer = [0, quarter, half, quarter]
print(*[answer[i // 90 % 4] for i in angles], sep='\n')


import sys
import math
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
degrees = []
for a0 in range(q):
	angle = int(input().strip())
	degrees.append(angle)

def hack(n):
	if n < 4:
		return n % 2 == 0
	n = (n - 4) % 7
	return n < 2 or n == 5

def create_matrix(n):
	matrix = [[0 for x in range(n)] for y in range(n)]
	for row in range(0, n):
		for column in range(0, n):
			if hack(((row + 1) * (column + 1)) ** 2):
				matrix[row][column] = '#'
			else:
				matrix[row][column] = '.'
	return matrix

def print_matrix(m):
	for row in m:
		print(*row)
	print('')
rot_mem = {}

def rotate_clockwise(matrix, degree):
	if degree in rot_mem:
		return rot_mem[degree]
	for i in range(1, int(degree / 90) + 1):
		matrix = list(zip(*matrix[::-1]))
	rot_mem[degree] = matrix
	return matrix

def naive_count(matrix, degree):
	count = 0
	matrix_rotate = rotate_clockwise(matrix, degree)
	for i in range(0, n):
		for j in range(0, n):
			if matrix[i][j] != matrix_rotate[i][j]:
				count = count + 1
	return count

def opt_count(matrix, degree):
	count = 0
	half = math.floor(len(matrix) / 2)
	matrix_rotate = rotate_clockwise(matrix, degree)
	range_n = range(0, n)
	for i in range_n:
		for j in range(0, half):
			if matrix[i][j] != matrix_rotate[i][j]:
				count = count + 1
	count = count * 2
	if len(matrix) % 2 != 0:
		for i in range_n:
			if matrix[i][half] != matrix_rotate[i][half]:
				count = count + 1
	return count

def round_degree(degree):
	degree = degree % 360
	if degree == 270:
		degree = 90
	return degree
count_mem = {}

def run(range_n):
	for n in range_n:
		matrix = create_matrix(n)
		for degree in degrees:
			count = 0
			degree = round_degree(degree)
			if degree in count_mem:
				count = count_mem[degree]
			else:
				count = opt_count(matrix, degree) if degree != 0 else 0
				count_mem[degree] = count
			print(count)
run([n])


import sys
dic = {1: 'Y', 3: 'Y', 6: 'Y', 0: 'Y', 2: 'X', 4: 'X', 5: 'X'}
Y_dic = {}
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
for i in range(1, n + 1):
	for j in range(i, n + 1):
		if dic[i ** 2 * j ** 2 % 7] == 'Y':
			Y_dic[i, j] = 1
			if i != j:
				Y_dic[j, i] = 1
transform = {}

def rotate_90(coordinate):
	return (coordinate[1], n + 1 - coordinate[0])
rotate_1 = 0
rotate_2 = 0
rotate_3 = 0
for y in Y_dic:
	temp = rotate_90(y)
	if temp not in Y_dic:
		rotate_1 += 2
	temp = rotate_90(temp)
	if temp not in Y_dic:
		rotate_2 += 2
	temp = rotate_90(temp)
	if temp not in Y_dic:
		rotate_3 += 2
transform[1] = rotate_1
transform[2] = rotate_2
transform[3] = rotate_3
for a0 in range(q):
	angle = int(input().strip())
	value = angle / 90 % 4
	if value == 0:
		print(0)
	else:
		print(transform[value])


import sys

def sum_M(x, y, mat):
	s = 0
	for i in range(1, x + 1):
		for j in range(1, y + 1):
			s += mat[i % 7][j % 7]
	return s
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
n1 = n % 7
n2 = n // 7
M = [[1, 1, 1, 1, 1, 1, 1], [1, 1, 0, 0, 0, 0, 1], [1, 0, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 1, 0], [1, 0, 1, 0, 0, 1, 0], [1, 0, 0, 1, 1, 0, 0], [1, 1, 0, 0, 0, 0, 1]]
mod7 = [1, 1, 0, 1, 0, 0, 1]
P90 = [[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0]]
P180 = [[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0]]
P270 = [[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0]]
for i in range(7):
	for j in range(7):
		if M[i][j] != M[j][(n1 + 1 - i) % 7]:
			P90[i][j] = 1
		if M[i][j] != M[(n1 + 1 - i) % 7][(n1 + 1 - j) % 7]:
			P180[i][j] = 1
		if M[i][j] != M[(n1 + 1 - j) % 7][i]:
			P270[i][j] = 1
count90 = sum_M(7, 7, P90)
count180 = sum_M(7, 7, P180)
count270 = sum_M(7, 7, P270)
for a0 in range(q):
	angle = int(input().strip()) % 360
	if angle == 0 or n1 == 6:
		print(0)
		continue
	elif angle == 90:
		count = n2 ** 2 * count90
		count += n2 * (sum_M(n1, 7, P90) + sum_M(7, n1, P90))
		count += sum_M(n1, n1, P90)
		print(count)
	elif angle == 180:
		count = n2 ** 2 * count180
		count += n2 * (sum_M(n1, 7, P180) + sum_M(7, n1, P180))
		count += sum_M(n1, n1, P180)
		print(count)
	elif angle == 270:
		count = n2 ** 2 * count90
		count += n2 * (sum_M(n1, 7, P270) + sum_M(7, n1, P270))
		count += sum_M(n1, n1, P270)
		print(count)


import sys

def h_bit(n):
	if n == 1:
		return 1
	return seq[(n - 2) % 7]
seq = [0, 1, 0, 0, 1, 1, 1]

def cell(i, j):
	return h_bit((i * j) ** 2)

def matrix(n):
	return [[cell(i + 1, j + 1) for j in range(n)] for i in range(n)]

def get_rot(row, col, n, rot):
	new_row = row
	if rot == 270 or rot == 180:
		new_row = n - row - 1
	new_col = col
	if rot == 90 or rot == 180:
		new_col = n - col - 1
	return (new_row, new_col)
compare_memo = {}

def compare(m, n, rot):
	if rot >= 360:
		return compare(m, n, rot % 360)
	if rot == 0:
		return 0
	if rot == 270:
		return compare(m, n, 90)
	if rot in compare_memo:
		return compare_memo[rot]
	diff = 0
	for row in range(n):
		for col in range(n):
			(rot_row, rot_col) = get_rot(row, col, n, rot)
			if m[rot_row][rot_col] != m[row][col]:
				diff += 1
	compare_memo[rot] = diff
	return diff
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
m = matrix(n)
for a0 in range(q):
	angle = int(input().strip())
	print(compare(m, n, angle))


import sys
checker = [False, False, True, False, True, True, False, False]

def HH(gen):
	pos = gen % 7
	return checker[pos]
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
matrix = [[HH((x + 1) * (y + 1) * ((x + 1) * (y + 1))) for x in range(n)] for y in range(n)]

def tp270(i, j):
	return matrix[n - i - 1][j]

def tp180(i, j):
	return matrix[n - i - 1][n - j - 1]

def tp90(i, j):
	return matrix[i][n - j - 1]

def tp0(i, j):
	return matrix[i][j]
ans = [-1, -1, -1, -1]

def calcAns(pos):
	if ans[pos] != -1:
		return ans[pos]
	else:
		ans[pos] = 0
		if pos == 1:
			func = tp90
		elif pos == 2:
			func = tp180
		elif pos == 3:
			func = tp270
		else:
			func = tp0
		for a in range(n):
			for b in range(n):
				if matrix[a][b] != func(a, b):
					ans[pos] += 1
		return ans[pos]
for a0 in range(q):
	angle = int(input().strip())
	translate = angle % 360 // 90
	print(calcAns(translate))


import sys

class Matrix:

	def __init__(self, n):
		self.n = n
		self.grid = []
		for i in range(1, n + 1):
			row = []
			for j in range(1, n + 1):
				row.append('Y' if self.parity((i * j) ** 2 - 1) else 'X')
			self.grid.append(row)
		self.differences = [0, 0, 0, 0]
		self.right = 0
		self.full = 0
		self.left = 0

	def parity(self, n):
		v = n % 7
		if v == 0 or v == 2 or v == 5 or (v == 6):
			return True
		else:
			return False

	def find_differences(self, n):
		right = 0
		full = 0
		left = 0
		for i in range(n):
			for j in range(n):
				if self.grid[i][j] != self.grid[n - (j + 1)][i]:
					right += 1
				if self.grid[i][j] != self.grid[n - (i + 1)][n - (j + 1)]:
					full += 1
				if self.grid[i][j] != self.grid[n - (j + 1)][i]:
					left += 1
		self.differences[1] = right
		self.differences[2] = full
		self.differences[3] = left
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
matrix = Matrix(n)
matrix.find_differences(n)
for a0 in range(q):
	angle = int(input().strip())
	print(matrix.differences[angle % 360 // 90])


(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
arr = [0, 0, 1, 0, 1, 1, 0]
grid = []
for i in range(n):
	row = []
	for j in range(n):
		product = (i + 1) * (j + 1)
		temp = product ** 2
		row.append(arr[temp % 7])
	grid.append(row)
differences = [0]
for a in [90, 180, 270]:
	numDifferences = 0
	if a == 90:
		for i in range(n):
			for j in range(n):
				if grid[i][j] != grid[n - 1 - j][i]:
					numDifferences += 1
		differences.append(numDifferences)
	elif a == 180:
		for i in range(n // 2):
			for j in range(n):
				if grid[i][j] != grid[n - 1 - i][n - 1 - j]:
					numDifferences += 2
		if n % 2 == 1:
			for i in range(n // 2):
				if grid[n // 2][i] != grid[n // 2][n - 1 - i]:
					numDifferences += 2
		differences.append(numDifferences)
	elif a == 270:
		for i in range(n):
			for j in range(n):
				if grid[i][j] != grid[j][n - 1 - i]:
					numDifferences += 1
		differences.append(numDifferences)
for a0 in range(q):
	angle = int(input().strip())
	angle = angle % 360
	print(differences[angle // 90])


import sys

def isEven(n):
	r = n % 7
	return 1 if r == 0 or r == 1 or r == 3 or (r == 6) else 0

def addToAns(a, b, c, d, ans):
	s = a + b + c + d
	if s == 0 or s == 4:
		return
	elif s == 1 or s == 3:
		ans[1] += 2
		ans[2] += 2
		ans[3] += 2
	elif a == c:
		ans[1] += 4
		ans[3] += 4
	else:
		ans[2] += 4
		ans[1] += 2
		ans[3] += 2

def getAns(n):
	ans = [0, 0, 0, 0]
	mid = n // 2 + 1
	for x in range(1, mid + n % 2):
		for y in range(1, mid):
			(x1, x2, x3, x4) = (x, n + 1 - y, n + 1 - x, y)
			(y1, y2, y3, y4) = (y, x, n + 1 - y, n + 1 - x)
			(a, b, c, d) = ((x1 * y1) ** 2, (x2 * y2) ** 2, (x3 * y3) ** 2, (x4 * y4) ** 2)
			(a, b, c, d) = (isEven(a), isEven(b), isEven(c), isEven(d))
			addToAns(a, b, c, d, ans)
	return ans
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
ans = getAns(n)
for a0 in range(q):
	angle = int(input().strip())
	print(ans[angle // 90 % 4])


import sys

def hack(n):
	if n == 0 or n == 1 or n == 3:
		return 1
	if n == 2:
		return 0
	else:
		return hack(n - 1) ^ hack(n - 3)
memo_hack = [hack(n) for n in range(7)]
op1 = [[0.489795918, -5.46029707e-14, 8.63270775e-13], [0.48979592, -0.40816327, -0.08163265], [0.48979592, 0.32653061, -0.6122449], [0.48979592, -0.08163265, -0.16326531], [0.48979592, 0.36734694, 0.69387755], [0.48979592, 0.53061224, -0.89795918], [0.0, 0.0, 0.0]]
op2 = [[0.612244898, -3.62015283e-14, 5.30636832e-13], [0.48979592, 0.16326531, -0.65306122], [0.44897959, -0.65306122, 1.51020408], [0.44897959, 0.16326531, 1.46938776], [0.48979592, -0.48979592, 0.12244898], [0.6122449, 0.16326531, -2.12244898], [0.0, 0.0, 0.0]]

def ops1(n):
	coefs = op1[n % 7]
	return round(coefs[0] * n ** 2 + coefs[1] * n + coefs[2])

def ops2(n):
	coefs = op2[n % 7]
	return round(coefs[0] * n ** 2 + coefs[1] * n + coefs[2])

def solution(n, rot):
	if rot == 0:
		return 0
	if rot == 1 or rot == 3:
		return ops1(n)
	else:
		return ops2(n)

def hackarr(c):
	return memo_hack[(c[0] * c[1]) ** 2 % 7]

def rot1(c, n):
	return (c[1], n - c[0] + 1)

def rot2(c, n):
	return (n - c[0] + 1, n - c[1] + 1)

def diag(n):
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			yield (i, j)
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
for a0 in range(q):
	angle = int(input().strip())
	rot = angle // 90 % 4
	print(solution(n, rot))


(n, q) = map(int, input().split())
x = [1, 1, 0, 1, 0, 0, 1]
a = []
for i in range(n):
	c = []
	for j in range(n):
		z = (i + 1) * (j + 1) * (i + 1) * (j + 1)
		p = z % 7
		c.append(x[p])
	a.append(c)
ans = [0]
o = a
for a0 in range(4):
	count = 0
	b = []
	for i in range(n):
		m = []
		for j in range(n):
			m.append(a[n - j - 1][i])
		b.append(m)
	for i in range(n):
		for j in range(n):
			if o[i][j] != b[i][j]:
				count = count + 1
	ans.append(count)
	a = b
for k in range(q):
	ang = int(input())
	ang = ang // 90
	ang = ang % 4
	print(ans[ang])


import sys

def corrected_angle(angle):
	return angle % 360 // 90

def hackonacci(n):
	pattern = [False, False, True, False, True, True, False]
	return pattern[n % 7]

def rotations(n):
	arr = gen(n)
	count90_270 = 0
	count180 = 0
	for i in range(n):
		for j in range(n):
			count90_270 += not arr[i][j] is arr[n - j - 1][i]
			count180 += not arr[i][j] is arr[n - i - 1][n - j - 1]
	return (count90_270, count180)

def gen(n):
	pattern = []
	for i in range(1, n + 1):
		pattern.append([])
		for j in range(1, n + 1):
			if hackonacci((i * j) ** 2):
				res = 'X'
			else:
				res = 'Y'
			pattern[i - 1].append(res)
	return pattern

def display(pattern):
	n = len(pattern)
	for i in range(n):
		for j in range(n):
			print(pattern[i][j], end=' ')
		print()
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
rot = rotations(n)
for a0 in range(q):
	angle = int(input().strip())
	ca = corrected_angle(angle)
	if ca == 0:
		print(0)
	elif ca == 1 or ca == 3:
		print(rot[0])
	elif ca == 2:
		print(rot[1])


(n, q) = [int(i) for i in input().split()]
V = [1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1]
d = {0: 0}
for _ in range(q):
	count = 0
	angle = int(input()) % 360
	if angle in d:
		print(d[angle])
	elif angle == 90 or angle == 270:
		for i in range(1, n + 1):
			k = 1
			for j in range(n, 0, -1):
				if V[((i * j) ** 2 - 1) % 56] != V[((i * k) ** 2 - 1) % 56]:
					count += 1
				k += 1
		d[90] = count
		d[270] = count
		print(d[angle])
	elif angle == 180:
		k = 1
		for i in range(n, 0, -1):
			l = 1
			for j in range(n, 0, -1):
				if V[((i * j) ** 2 - 1) % 56] != V[((k * l) ** 2 - 1) % 56]:
					count += 1
				l += 1
			k += 1
		d[angle] = count
		print(d[angle])


import sys

def diffc(a, b, n):
	cnt = 0
	for i in range(n):
		for j in range(n):
			if a[i][j] != b[i][j]:
				cnt += 1
	return cnt
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
hack = ['Y', 'Y', 'X', 'Y', 'X', 'X', 'Y', 'Y', 'Y']
hackm = [[] for i in range(n)]
for i in range(n):
	for j in range(n):
		hackm[i].append(hack[pow((i + 1) * (j + 1), 2, 7)])
hackm[0][0] = 'Y'
ninety = list(zip(*hackm[::-1]))
eighty = list(zip(*ninety[::-1]))
two = list(zip(*eighty[::-1]))
ans = [0]
ans.append(diffc(hackm, ninety, n))
ans.append(diffc(hackm, eighty, n))
ans.append(diffc(hackm, two, n))
for a0 in range(q):
	angle = int(input().strip())
	local = angle // 90
	local = local % 4
	print(ans[local])


from pprint import pprint
pattern = [1, 1, 0, 1, 0, 0, 1]
m = len(pattern)
modkey = dict(zip(range(m), pattern))

def hack(x):
	return modkey[x % m]
(n, q) = map(int, input().split())
ar = [None]
for i in range(1, n + 1):
	ar.append([hack((i * x) ** 2) for x in range(1, m + 1)])
ret = []
repeats = n // 7
remainder = n % 7
for i in range(1, n + 1):
	t = []
	fullval = sum((0 if ar[i][j] == ar[n + 1 - i][j] else 1 for j in range(7)))
	partval = sum((0 if ar[i][j] == ar[n + 1 - i][j] else 1 for j in range(remainder)))
	t.append(repeats * fullval + partval)
	fullval = sum((0 if ar[i][j] == ar[n + 1 - i][-((-remainder + 1 + j) % 7)] else 1 for j in range(7)))
	partval = sum((0 if ar[i][j] == ar[n + 1 - i][-((-remainder + 1 + j) % 7)] else 1 for j in range(remainder)))
	t.append(repeats * fullval + partval)
	fullval = sum((0 if ar[i][j] == ar[i][-((-remainder + 1 + j) % 7)] else 1 for j in range(7)))
	partval = sum((0 if ar[i][j] == ar[i][-((-remainder + 1 + j) % 7)] else 1 for j in range(remainder)))
	t.append(repeats * fullval + partval)
	ret.append(t)
scores = dict()
scores[0] = 0
scores[90] = sum((x[0] for x in ret))
scores[180] = sum((x[1] for x in ret))
scores[270] = sum((x[2] for x in ret))
for a0 in range(q):
	angle = int(input())
	angle = angle % 360
	print(scores[angle])


import sys, copy
h = [['Y', 'X', 'X', 'X', 'X', 'Y', 'Y'], ['X', 'X', 'Y', 'Y', 'X', 'X', 'Y'], ['X', 'Y', 'X', 'X', 'Y', 'X', 'Y'], ['X', 'Y', 'X', 'X', 'Y', 'X', 'Y'], ['X', 'X', 'Y', 'Y', 'X', 'X', 'Y'], ['Y', 'X', 'X', 'X', 'X', 'Y', 'Y'], ['Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y']]
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
m = []
for i in range(n):
	m.append([])
for i in range(n):
	for j in range(n):
		m[i].append(h[i % 7][j % 7])
(m1, m2, m3) = ([], [], [])
for i in range(n):
	m1.append([])
	m2.append([])
	m3.append([])
result = [0, 0, 0, 0]
for i in range(n):
	for j in range(n):
		m1[i].append(m[n - j - 1][i])
count = 0
for i in range(n):
	for j in range(n):
		if m[i][j] != m1[i][j]:
			count += 1
result[1] = count
for i in range(n):
	for j in range(n):
		m2[i].append(m[n - j - 1][n - i - 1])
count = 0
for i in range(n):
	for j in range(n):
		if m[i][j] != m2[i][j]:
			count += 1
result[2] = count
for i in range(n):
	for j in range(n):
		m3[i].append(m[j][n - i - 1])
count = 0
for i in range(n):
	for j in range(n):
		if m[i][j] != m3[i][j]:
			count += 1
result[3] = count
for a0 in range(q):
	angle = int(input().strip())
	if angle >= 360:
		while angle >= 360:
			angle -= 360
	num = int(angle / 90)
	print(result[num])