solutions: ["def entry(i, j):\n\ti = i % 7\n\tj = j % 7\n\tp = i * i * j * j % 7\n\tfoo = [1, 1, 0, 1, 0, 0, 1, 1]\n\treturn foo[p]\n\ndef rot90(n, i, j):\n\treturn (j, n + 1 - i)\n(n, num_probs) = (int(x) for x in input().split())\ndiff90 = 0\ndiff180 = 0\nfor i in range(1, n + 1):\n\tfor j in range(1, n + 1):\n\t\tval0 = entry(i, j)\n\t\t(i90, j90) = rot90(n, i, j)\n\t\tval90 = entry(i90, j90)\n\t\t(i180, j180) = rot90(n, i90, j90)\n\t\tval180 = entry(i180, j180)\n\t\tif val0 != val90:\n\t\t\tdiff90 += 1\n\t\tif val0 != val180:\n\t\t\tdiff180 += 1\nfor prob in range(num_probs):\n\tangle = int(input())\n\tangle = angle % 360\n\tif angle == 0:\n\t\tprint(0)\n\tif angle == 90 or angle == 270:\n\t\tprint(diff90)\n\tif angle == 180:\n\t\tprint(diff180)\n", "import sys\nimport itertools\nimport operator\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nHSeries = [1, 1, 0, 1, 0, 0, 1, 1]\nmatrix = []\nfor i in range(n):\n\tl = []\n\tfor j in range(n):\n\t\tl.append(HSeries[((i + 1) * (j + 1)) ** 2 % 7])\n\tmatrix.append(l)\nflatten = list(itertools.chain(*matrix))\nrotnum = [0, -1, -1, -1]\nfor a0 in range(q):\n\tangle = int(input().strip()) % 360 // 90\n\tif rotnum[angle] != -1:\n\t\tprint(rotnum[angle])\n\telse:\n\t\trotate = matrix\n\t\tfor _ in range(angle):\n\t\t\trotate = [list(t) for t in zip(*rotate[::-1])]\n\t\trotate = list(itertools.chain(*rotate))\n\t\tdiff = sum(list(map(abs, list(map(operator.sub, flatten, rotate)))))\n\t\tprint(diff)\n\t\trotnum[angle] = diff\n", "import sys\nfrom time import time\n\ndef h_gen():\n\t(a, b, c) = (1, 2, 3)\n\tfor v in (a, b, c):\n\t\tyield v\n\twhile True:\n\t\t(a, b, c) = (b, c, a + 2 * b + 3 * c)\n\t\tyield c\n\ndef hsqr_gen():\n\t(u, u2) = (1, 1)\n\tfor (i, h) in enumerate(h_gen()):\n\t\tif i + 1 == u2:\n\t\t\tyield (u, h)\n\t\t\tu += 1\n\t\t\tu2 = u * u\n\ndef r_gen():\n\tcache = (0, 0, 0, 0, 1, 1, 1)\n\tyield 1\n\twhile True:\n\t\tyield from cache\nrcache = (1, 0, 0, 0, 0, 1, 1)\n\ndef get_r(n):\n\tu = (n - 1) % len(rcache)\n\treturn rcache[u]\n\ndef get_matrix(n):\n\treturn [[get_r((i + 1) * (j + 1)) for j in range(n)] for i in range(n)]\n\ndef rotate_90(m):\n\tnew_m = []\n\tfor r in range(len(m)):\n\t\tnew_m.append([m[i][r] for i in range(len(m) - 1, -1, -1)])\n\treturn new_m\n\ndef test(n):\n\tfor (i, h) in enumerate(h_gen()):\n\t\tprint(h, end=' ', file=sys.stderr)\n\t\tif i == n:\n\t\t\tbreak\n\tprint(file=sys.stderr)\n\tfor (i, h) in enumerate(hsqr_gen()):\n\t\t(_, v) = h\n\t\tprint(v % 2, end=' ', file=sys.stderr)\n\t\tif i == n:\n\t\t\tbreak\n\tprint(file=sys.stderr)\n\tfor (i, r) in enumerate(r_gen()):\n\t\tprint(r, end=' ', file=sys.stderr)\n\t\tif i == n:\n\t\t\tbreak\n\tprint(file=sys.stderr)\n\tfor i in range(1, n):\n\t\tprint(get_r(i), end=' ', file=sys.stderr)\n\tprint(file=sys.stderr)\n\tm = get_matrix(n)\n\tprint(m, file=sys.stderr)\n\tm = rotate_90(m)\n\tprint(m, file=sys.stderr)\n\ndef get_cache(n):\n\n\tdef count(m1, m2):\n\t\tsm = 0\n\t\tfor i in range(n):\n\t\t\tfor j in range(n):\n\t\t\t\tsm += m1[i][j] ^ m2[i][j]\n\t\treturn sm\n\tm = get_matrix(n)\n\tmm = [m]\n\tfor _ in range(3):\n\t\tmm.append(rotate_90(mm[-1]))\n\tcache = [0] * len(mm)\n\tfor i in range(1, len(mm)):\n\t\tcache[i] = count(mm[0], mm[i])\n\treturn cache\n\ndef solve(cache, angle):\n\tr = angle // 90 % 4\n\treturn cache[r]\ntm = time()\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\ncache = get_cache(n)\nprint('cache=%s' % cache, file=sys.stderr)\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tprint(solve(cache, angle))\nprint('time elapsed: %s' % (time() - tm), file=sys.stderr)\n", "import operator\n(n, q) = map(int, input().split())\nchecker = (1, 0, 1, 0, 0, 1, 1)\nar = tuple((tuple((checker[(i * i * j * j - 1) % 7] for i in range(1, n + 1))) for j in range(1, n + 1)))\n\ndef rotate(mat):\n\treturn tuple(zip(*reversed(mat)))\nchanges = [0]\ntemp = ar\nfor i in range(3):\n\ttemp = rotate(temp)\n\tchanges.append(sum((sum(map(operator.ne, ar[i], temp[i])) for i in range(n))))\nfor _ in range(q):\n\tprint(changes[int(input()) // 90 % 4])\n", "def hackonacci(n):\n\treturn [1, 0, 1, 0, 0, 1, 1][(n - 1) % 7]\n\ndef solve(n, A):\n\tM = [[hackonacci((i * j) ** 2) for j in range(1, n + 1)] for i in range(1, n + 1)]\n\tcount = {0: 0, 90: 0, 180: 0, 270: 0}\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tcount[90] += M[i][j] ^ M[j][n - 1 - i]\n\t\t\tcount[180] += M[i][j] ^ M[n - 1 - i][n - 1 - j]\n\t\t\tcount[270] += M[i][j] ^ M[n - 1 - j][i]\n\treturn list((count[a % 360] for a in A))\n(n, q) = map(int, input().split())\nA = list((int(input()) for _ in range(q)))\nprint('\\n'.join(map(str, solve(n, A))))\n", "(n, q) = map(int, input().split())\n\ndef hackonacci_fun(i, period=(1, 0, 1, 0, 0, 1, 1)):\n\treturn period[(i - 1) % 7]\nhack_matrix = n * n * [0]\nfor i in range(n):\n\thack_matrix[i * n + i] = hackonacci_fun((i + 1) ** 4)\n\tfor j in range(i + 1, n):\n\t\thack_matrix[i * n + j] = hack_matrix[j * n + i] = hackonacci_fun(((i + 1) * (j + 1)) ** 2)\nrot90 = 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]))\nrot180 = 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]))\nrot = {0: 0, 90: rot90, 180: rot180, 270: rot270}\nfor _ in range(q):\n\tprint(rot[int(input()) % 360])\n", "import sys\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nparity_helper = [1, 1, 0, 1, 0, 0, 1]\nrot_90 = 0\nrot_180 = 0\nfor i in range(1, n // 2 + 1):\n\tfor j in range(1, n + 1):\n\t\tif parity_helper[(i * j) ** 2 % 7] != parity_helper[(j * (1 + n - i)) ** 2 % 7]:\n\t\t\trot_90 += 1\n\t\tif parity_helper[(i * j) ** 2 % 7] != parity_helper[((1 + n - i) * (1 + n - j)) ** 2 % 7]:\n\t\t\trot_180 += 1\nrot_90 = 2 * rot_90\nrot_180 = 2 * rot_180\nif n % 2 == 1:\n\ti = n // 2 + 1\n\tfor j in range(1, n + 1):\n\t\tif parity_helper[(i * j) ** 2 % 7] != parity_helper[(i * (1 + n - j)) ** 2 % 7]:\n\t\t\trot_180 += 1\nrot = [0, rot_90, rot_180, rot_90]\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tprint(rot[int(angle / 90 % 4)])\n", "import sys\nres = 'YYXYXXY'\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nans = dict()\nans[0] = 0\nans[90] = 0\nans[180] = 0\nans[270] = 0\n\ndef cc(i, j):\n\treturn res[(i * j) ** 2 % 7]\nfor i in range(1, n + 1):\n\tfor j in range(1, n + 1):\n\t\tc = res[(i * j) ** 2 % 7]\n\t\tif c != cc(j, n - i + 1):\n\t\t\tans[90] += 1\n\t\tif c != cc(n - i + 1, n - j + 1):\n\t\t\tans[180] += 1\n\t\tif c != cc(n - j + 1, i):\n\t\t\tans[270] += 1\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tprint(ans[angle % 360])\n", "(n, q) = map(int, input().split())\nqueries = (int(input()) for _ in range(q))\nh = [1, 2, 3]\nfor _ in range(11):\n\th.append(h[-1] + 2 * h[-2] + 3 * h[-3])\nh = [i & 1 for i in h]\nmatrix = bytearray(n ** 2)\nk = 0\nfor i in range(1, n + 1):\n\tfor j in range(1, n + 1):\n\t\tmatrix[k] = h[((i * j) ** 2 - 1) % 14]\n\t\tk += 1\ndifferences = [0, None, None, None]\n(ndiv, nmod) = divmod(n, 2)\ndiff = 0\nfor i in range(ndiv):\n\tfor j in range(n):\n\t\tif matrix[n * i + j] != matrix[n * j + n - 1 - i]:\n\t\t\tdiff += 2\nif nmod:\n\tfor j in range(n):\n\t\tif matrix[n * ndiv + j] != matrix[n * j + n - 1 - ndiv]:\n\t\t\tdiff += 1\ndifferences[1] = differences[3] = diff\ndiff = 0\nfor i in range(ndiv):\n\tfor j in range(n):\n\t\tif matrix[n * i + j] != matrix[n * (n - 1 - j) + n - 1 - i]:\n\t\t\tdiff += 2\nif nmod:\n\tfor j in range(n):\n\t\tif matrix[n * ndiv + j] != matrix[n * (n - 1 - j) + n - 1 - ndiv]:\n\t\t\tdiff += 1\ndifferences[2] = diff\nfor q in queries:\n\tprint(differences[q % 360 // 90])\n", "import sys\n\ndef rotated(M):\n\tres = []\n\tfor r in range(n):\n\t\tres.append([])\n\t\tfor c in range(n):\n\t\t\tres[-1].append(M[n - 1 - c][r])\n\treturn res\nQ = [1, 1, 0, 1, 0, 0, 1]\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nM = []\nfor r in range(1, n + 1):\n\tM.append([])\n\tfor c in range(1, n + 1):\n\t\tM[-1].append(Q[r * r * c * c % 7])\nA = {0: 0}\nAM = M\nfor ang in [90, 180, 270]:\n\tAM = rotated(AM)\n\tdiff = 0\n\tfor r in range(n):\n\t\tfor c in range(n):\n\t\t\tif AM[r][c] != M[r][c]:\n\t\t\t\tdiff += 1\n\tA[ang] = diff\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tprint(A[angle % 360])\n", "import sys\nseries = [1, 0, 1, 0, 0, 1, 1]\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\n\ndef rotateMatrix(orgMatrix, i):\n\tif i == 0:\n\t\treturn orgMatrix\n\telif i == 1:\n\t\treturn list(zip(*orgMatrix[::-1]))\n\telif i == 2:\n\t\torgMatrix = list(zip(*orgMatrix[::-1]))\n\t\treturn list(zip(*orgMatrix[::-1]))\n\telif i == 3:\n\t\torgMatrix = list(zip(*orgMatrix[::-1]))\n\t\torgMatrix = list(zip(*orgMatrix[::-1]))\n\t\treturn list(zip(*orgMatrix[::-1]))\nanswer = [None, None, None, None]\norgMatrix = []\nfor i in range(1, n + 1):\n\tx = []\n\tfor j in range(1, n + 1):\n\t\tx.append(series[(i * j) ** 2 % 7 - 1])\n\torgMatrix.append(x)\nfor a0 in range(q):\n\tangle = int(input().strip())\n\trot = angle % 360 // 90\n\tif answer[rot] is None:\n\t\taltMatrix = rotateMatrix(orgMatrix, rot)\n\t\tcount = 0\n\t\tfor i in range(n):\n\t\t\tfor j in range(n):\n\t\t\t\tif orgMatrix[i][j] != altMatrix[i][j]:\n\t\t\t\t\tcount += 1\n\t\tanswer[rot] = count\n\tprint(answer[rot])\n", "import sys\n(n, q) = map(int, input().strip().split(' '))\nmemo = ['X', 'X', 'Y', 'Y', 'Y', 'X', 'Y']\n\ndef mat(n, memo):\n\tif n == 1:\n\t\treturn 'Y'\n\telif n == 2:\n\t\treturn 'X'\n\telif n == 3:\n\t\treturn 'Y'\n\telse:\n\t\tm = (n - 4) % 7\n\t\treturn memo[m]\narr = []\nNor = {}\nfinal = {0: 0}\nfor i in range(1, n + 1):\n\tlist1 = []\n\tfor j in range(1, n + 1):\n\t\tfindnum = (i * j) ** 2\n\t\tif findnum not in Nor:\n\t\t\telement = mat(findnum, memo)\n\t\t\tNor[findnum] = element\n\t\t\tlist1.append(element)\n\t\telse:\n\t\t\telement = Nor[findnum]\n\t\t\tlist1.append(element)\n\tarr.append(list1)\nfor i in range(q):\n\tarr1 = arr\n\tcount = 0\n\tnmbrturns = int(int(input().strip()) / 90)\n\tif nmbrturns >= 4:\n\t\tnmbrturns = nmbrturns % 4\n\tif nmbrturns not in final:\n\t\tfor i in range(nmbrturns):\n\t\t\tTurn = list(zip(*arr1[::-1]))\n\t\t\tarr1 = Turn\n\t\tfor i in range(n):\n\t\t\tfor j in range(n):\n\t\t\t\tif arr[i][j] != arr1[i][j]:\n\t\t\t\t\tcount += 1\n\t\tfinal[nmbrturns] = count\n\t\tprint(count)\n\telse:\n\t\tprint(final[nmbrturns])\n", "import sys\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nlookup = [0, 0, 0, 0]\nhackonacciEven = [1, 1, 0, 1, 0, 0, 1]\n\ndef hackEven(n):\n\treturn hackonacciEven[n % 7]\nfor i in range(1, n + 1):\n\ti_ = i % 7\n\tin_ = (n - i + 1) % 7\n\tfor j in range(1, n + 1):\n\t\tj_ = j % 7\n\t\tjn_ = (n - j + 1) % 7\n\t\tval = hackEven((i_ * j_) ** 2)\n\t\tval180 = hackEven((in_ * jn_) ** 2)\n\t\tval90 = hackEven((i_ * jn_) ** 2)\n\t\tif val != val180:\n\t\t\tlookup[2] = lookup[2] + 1\n\t\tif val != val90:\n\t\t\tlookup[1] = lookup[1] + 1\nlookup[3] = lookup[1]\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tangle = angle % 360\n\tprint(lookup[angle // 90])\n", "import sys\nmat = '*----**\\n--**--*\\n-*--*-*\\n-*--*-*\\n--**--*\\n*----**\\n*******'.splitlines()\n\ndef diff(l1, l2):\n\tflat1 = (item for sublist in l1 for item in sublist)\n\tflat2 = (item for sublist in l2 for item in sublist)\n\tret = 0\n\tfor (a, b) in zip(flat1, flat2):\n\t\tif a != b:\n\t\t\tret += 1\n\treturn ret\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nmatrix = []\nfor row in range(n):\n\tr = []\n\tfor col in range(n):\n\t\tr.append(mat[row % 7][col % 7])\n\tmatrix.append(r)\nangle_cache = {0: 0}\nfor a0 in range(q):\n\tangle = int(input().strip()) % 360 // 90\n\tif angle not in angle_cache:\n\t\tif angle in (1, 3):\n\t\t\trotated_matrix = zip(*matrix[::-1])\n\t\tif angle == 2:\n\t\t\trotated_matrix = (x[::-1] for x in matrix[::-1])\n\t\tangle_cache[angle] = diff(matrix, rotated_matrix)\n\tprint(angle_cache[angle])\n", "import sys\n\ndef hackonacci_is_even(n):\n\tn = n % 7\n\tif n == 0:\n\t\treturn False\n\tif n == 1:\n\t\treturn False\n\tif n == 2:\n\t\treturn True\n\tif n == 3:\n\t\treturn False\n\tif n == 4:\n\t\treturn True\n\tif n == 5:\n\t\treturn True\n\treturn False\n\ndef query(A, angle):\n\ttry:\n\t\treturn mem[angle]\n\texcept:\n\t\tres = 0\n\t\tif angle == 90 or angle == 270:\n\t\t\tfor i in range(n - 1, -1, -1):\n\t\t\t\tfor j in range(0, n):\n\t\t\t\t\tif A[i][j] != A[j][n - 1 - i]:\n\t\t\t\t\t\tres += 1\n\t\telif angle == 180:\n\t\t\tfor i in range(n - 1, -1, -1):\n\t\t\t\tfor j in range(n - 1, -1, -1):\n\t\t\t\t\tif A[i][j] != A[n - 1 - i][n - 1 - j]:\n\t\t\t\t\t\tres += 1\n\t\tmem[angle] = res\n\t\treturn res\nmem = {}\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nA = [[True for i in range(n)] for j in range(n)]\nfor i in range(0, n):\n\tfor j in range(i, n):\n\t\tis_even = hackonacci_is_even(((i + 1) * (j + 1)) ** 2)\n\t\tA[i][j] = is_even\n\t\tA[j][i] = is_even\nfor a0 in range(q):\n\tangle = int(input().strip()) % 360\n\tprint(query(A, angle))\n", "import sys\n\ndef hackonacci(num):\n\tif num == 1:\n\t\treturn 'Y'\n\telse:\n\t\tr = (num - 1) % 7\n\t\tif r in (1, 3, 4):\n\t\t\treturn 'X'\n\t\telse:\n\t\t\treturn 'Y'\n\ndef rotate(m, degree):\n\tif degree == 0:\n\t\treturn m\n\telif degree > 0:\n\t\treturn rotate(list(zip(*m[::-1])), degree - 90)\n\telse:\n\t\treturn rotate(list(zip(*m[::-1])), degree + 90)\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nmatrix = []\nfor i in range(1, n + 1):\n\trow = []\n\tfor j in range(1, n + 1):\n\t\trow.append(hackonacci((i * j) ** 2))\n\tmatrix.append(row)\ncounts = [0, 0, 0, 0]\nflags = [True, False, False, False]\nfor a0 in range(q):\n\tabs_angle = int(input().strip()) % 360\n\ta_idx = abs_angle // 90\n\tcount = 0\n\tif flags[a_idx]:\n\t\tcount = counts[a_idx]\n\telse:\n\t\tmatrix_rot = list(rotate(matrix, abs_angle))\n\t\tfor i in range(n):\n\t\t\trr = list(matrix_rot[i])\n\t\t\tfor j in range(n):\n\t\t\t\tif matrix[i][j] != rr[j]:\n\t\t\t\t\tcount += 1\n\t\tflags[a_idx] = True\n\t\tcounts[a_idx] = count\n\tprint(count)\n", "def char(i, j):\n\ti %= 7\n\tj %= 7\n\treturn [1, 1, 0, 1, 0, 0, 1][i * i * j * j % 7]\nqrtr = -1\nhalf = -1\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nN = n + 1\nfor _ in range(q):\n\tangle = int(input().strip()) % 360\n\tif angle == 0:\n\t\tprint(0)\n\telif angle == 180:\n\t\tif half < 0:\n\t\t\thalf = sum((char(i, j) ^ char(N - i, N - j) for i in range(1, N) for j in range(1, N)))\n\t\tprint(half)\n\telse:\n\t\tif qrtr < 0:\n\t\t\tqrtr = sum((char(i, j) ^ char(j, N - i) for i in range(1, N) for j in range(1, N)))\n\t\tprint(qrtr)\n", "from pprint import pprint\nis_odd = lambda x: x % 2 != 0\nrotate = lambda grid: [tuple(reversed(row)) for row in zip(*grid)]\ncompare = lambda a, b: sum((sum((a[i][j] != b[i][j] for i in range(n))) for j in range(n)))\n\ndef hacko_odd(x):\n\tif x < 3:\n\t\treturn x % 2\n\telse:\n\t\treturn [1, 0, 0, 1, 1, 1, 0][(x - 3) % 7]\n(n, q) = map(int, input().split())\ngrids = {0: [[hacko_odd((row * col) ** 2) for col in range(1, n + 1)] for row in range(1, n + 1)]}\nfor deg in range(90, 360, 90):\n\tgrids[deg] = rotate(grids[deg - 90])\nresults = [0] + [compare(grids[0], grids[deg]) for deg in range(90, 360, 90)]\nfor _ in range(q):\n\tprint(results[int(input()) % 360 // 90])\n", "import sys\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\n\ndef hack(n):\n\tn = n % 7\n\tif n in [2, 4, 5]:\n\t\treturn 'X'\n\telse:\n\t\treturn 'Y'\nans = {0: 0}\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tangle = angle % 360\n\tif angle in ans.keys():\n\t\tprint(ans[angle])\n\telif angle != 180:\n\t\tcount = 0\n\t\tfor i in range(1, n + 1):\n\t\t\tfor j in range(1, n + 1):\n\t\t\t\tif hack((i * j) ** 2) != hack(((n - i + 1) * j) ** 2):\n\t\t\t\t\tcount += 1\n\t\tprint(count)\n\t\tans[90] = count\n\t\tans[270] = count\n\telse:\n\t\tcount = 0\n\t\tfor i in range(1, n + 1):\n\t\t\tfor j in range(1, n + 1):\n\t\t\t\tif hack((i * j) ** 2) != hack(((n - i + 1) * (n - j + 1)) ** 2):\n\t\t\t\t\tcount += 1\n\t\tprint(count)\n\t\tans[180] = count\n", "import sys\n\ndef hack(n):\n\tx = 1\n\ty = 2\n\tz = 3\n\tif n == 1:\n\t\treturn False\n\tif n == 2:\n\t\treturn True\n\tif n == 3:\n\t\treturn False\n\ta = [True, True, False, False, False, True, False]\n\treturn a[(n - 4) % 7]\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nans90 = ans180 = ans270 = 0\nhackonaki = [['Y' for x in range(n + 1)] for x in range(n + 1)]\nfor i in range(1, n + 1):\n\tfor j in range(i, n + 1):\n\t\tif hack(i * j * i * j):\n\t\t\thackonaki[i][j] = 'X'\n\t\t\thackonaki[j][i] = 'X'\nfor i in range(1, n + 1):\n\tfor j in range(1, n + 1):\n\t\tif hackonaki[i][j] != hackonaki[j][n - i + 1]:\n\t\t\tans90 += 1\n\t\tif hackonaki[i][j] != hackonaki[n - i + 1][n - j + 1]:\n\t\t\tans180 += 1\n\t\tif hackonaki[i][j] != hackonaki[n - j + 1][i]:\n\t\t\tans270 += 1\nres = {}\nres[0] = 0\nres[90] = ans90\nres[180] = ans180\nres[270] = ans270\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tangle = angle % 360\n\tprint(res[angle])\n", "import sys\n\ndef rotate_90(mat):\n\trotated_90 = zip(*mat[::-1])\n\treturn list(rotated_90)\n\ndef compare_mat(arr1, arr2):\n\tres = 0\n\tnn = len(arr1)\n\tfor i in range(nn):\n\t\tfor j in range(nn):\n\t\t\tres += int(arr1[i][j] != arr2[i][j])\n\treturn res\nFACCO = [1, 1, 0, 1, 0, 0, 1]\nFACCO1 = set([0, 1, 3, 6])\n\ndef create_mat(n):\n\tmat = []\n\tfor i in range(n):\n\t\tmat.append([0] * n)\n\tfor i in range(n):\n\t\tfor j in range(i, n):\n\t\t\tij2 = (i + 1) * (i + 1) * (j + 1) * (j + 1) % 7\n\t\t\tif ij2 in FACCO1:\n\t\t\t\tmat[i][j] = 1\n\t\t\tif i != j:\n\t\t\t\tmat[j][i] = mat[i][j]\n\treturn mat\n\ndef process(n, angles):\n\tangles_values_calculated = [0, 0, 0, 0]\n\tangles_transformed = [ang % 360 for ang in angles]\n\tangles_to_calculate = set(angles_transformed)\n\tcalculate = True\n\tif len(angles_to_calculate) == 1 and list(angles_to_calculate)[0] == 0:\n\t\tcalculate = False\n\tif calculate:\n\t\tmat = create_mat(n)\n\t\tmat_angle_90 = rotate_90(mat)\n\t\tangles_values_calculated[1] = compare_mat(mat, mat_angle_90)\n\t\tmat_angle_180 = rotate_90(mat_angle_90)\n\t\tangles_values_calculated[2] = compare_mat(mat, mat_angle_180)\n\t\tmat_angle_270 = rotate_90(mat_angle_180)\n\t\tangles_values_calculated[3] = compare_mat(mat, mat_angle_270)\n\tfor angle in angles_transformed:\n\t\tprint(angles_values_calculated[angle // 90])\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nangles = []\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tangles.append(angle)\nprocess(n, angles)\n", "hackonacci = dict()\nfor i in range(1, 15):\n\tfor j in range(i, 15):\n\t\tcurr = (i * j) ** 2\n\t\tcurr %= 7\n\t\th = '1010011'[curr - 1]\n\t\thackonacci[i % 7, j % 7] = h\n\t\thackonacci[j % 7, i % 7] = h\nimport sys\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nmat = [[0 for i in range(n)] for j in range(n)]\nfor i in range(n):\n\tfor j in range(i, n):\n\t\tmat[i][j] = mat[j][i] = hackonacci[(i + 1) % 7, (j + 1) % 7]\nmat_270 = [[mat[n - 1 - i][j] for j in range(n)] for i in range(n)]\nmat_180 = [[mat[n - 1 - i][n - 1 - j] for j in range(n)] for i in range(n)]\nmat_90 = [[mat[i][n - 1 - j] for j in range(n)] for i in range(n)]\n(a1, a2, a3) = (0, 0, 0)\nfor i in range(n):\n\tfor j in range(n):\n\t\tif mat[i][j] != mat_90[i][j]:\n\t\t\ta1 += 1\n\t\tif mat[i][j] != mat_180[i][j]:\n\t\t\ta2 += 1\n\t\tif mat[i][j] != mat_270[i][j]:\n\t\t\ta3 += 1\nfor i in range(q):\n\tangle = int(input()) % 360\n\tif angle == 0:\n\t\tprint(0)\n\telif angle == 90:\n\t\tprint(a1)\n\telif angle == 180:\n\t\tprint(a2)\n\telse:\n\t\tprint(a3)\n", "import sys\nhackonacci_pattern = 'YXYXXYY'\n\ndef hackonacci_matrix(rows, cols):\n\tmatrix = []\n\tfor r in range(1, rows + 1):\n\t\trow = []\n\t\tfor c in range(1, cols + 1):\n\t\t\ti = (r * c) ** 2\n\t\t\trow.append(hackonacci_pattern[(i - 1) % 7])\n\t\tmatrix.append(''.join(row))\n\treturn matrix\n\ndef rotate_track(row, col, rows, cols):\n\trow_end = rows - 1\n\tcol_end = cols - 1\n\ttrack = []\n\tfor i in range(col_end):\n\t\ttrack.append((row + 0, col + i))\n\tfor i in range(row_end):\n\t\ttrack.append((row + i, col + col_end))\n\tfor i in range(col_end, 0, -1):\n\t\ttrack.append((row + row_end, col + i))\n\tfor i in range(row_end, 0, -1):\n\t\ttrack.append((row + i, col + 0))\n\treturn track\n\ndef rotate(matrix, angle):\n\tdiff_count = 0\n\tn = len(matrix)\n\t(row, col) = (0, 0)\n\twhile n > 1:\n\t\tL = []\n\t\ttrack = rotate_track(row, col, n, n)\n\t\tfor (r, c) in track:\n\t\t\tL.append(matrix[r][c])\n\t\ti = (n - 1) * (angle // 90)\n\t\tR = L[-i:] + L[:-i]\n\t\tcount = sum((1 for (a, b) in zip(L, R) if a != b))\n\t\tdiff_count += count\n\t\tn -= 2\n\t\trow += 1\n\t\tcol += 1\n\treturn diff_count\n(n, q) = (int(v) for v in input().strip().split(' '))\nmatrix = hackonacci_matrix(n, n)\ncache = {}\nfor a0 in range(q):\n\tangle = int(input().strip()) % 360\n\tresult = 0\n\tif angle > 0:\n\t\tif angle not in cache:\n\t\t\tcache[angle] = rotate(matrix, angle)\n\t\tresult = cache[angle]\n\tprint(result)\n", "(n, q) = [int(x) for x in input().split()]\ng = []\nd = [1, 1, 0, 1, 0, 0, 1, 1]\n\ndef pr(l):\n\tfor x in l:\n\t\tfor y in x:\n\t\t\tprint(y, end='')\n\t\tprint('\\r')\n\tprint('\\r')\nfor i in range(1, n + 1):\n\tg.append([d[i * i * j * j % 7] for j in range(1, n + 1)])\n\ndef df(k, l):\n\ts = 0\n\tfor x in range(n):\n\t\tfor y in range(n):\n\t\t\tif k[x][y] != l[x][y]:\n\t\t\t\ts += 1\n\treturn s\ng1 = list(zip(*g[::-1]))\no1 = df(g, g1)\ng2 = list(zip(*g1[::-1]))\no2 = df(g, g2)\ng3 = list(zip(*g2[::-1]))\no3 = df(g, g3)\nfor a0 in range(q):\n\ta = int(input().strip())\n\ta = a % 360\n\ta = a // 90\n\tif a == 1:\n\t\tprint(o1)\n\telif a == 2:\n\t\tprint(o2)\n\telif a == 3:\n\t\tprint(o3)\n\telse:\n\t\tprint(0)\n", "import sys\ncache = [1, 1, 0, 1, 0, 0, 1]\n\ndef hackonacci(n):\n\treturn cache[n % 7]\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nmatrix = [[hackonacci(((i + 1) * (j + 1)) ** 2) for i in range(n)] for j in range(n)]\nresults = [0, None, None, None]\ncount = 0\nfor i in range(n):\n\tfor j in range(n):\n\t\tcount += matrix[i][j] != matrix[j][n - i - 1]\nresults[1] = count\ncount = 0\nfor i in range(n):\n\tfor j in range(n):\n\t\tcount += matrix[i][j] != matrix[n - i - 1][n - j - 1]\nresults[2] = count\ncount = 0\nfor i in range(n):\n\tfor j in range(n):\n\t\tcount += matrix[i][j] != matrix[n - j - 1][i]\nresults[3] = count\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tprint(results[angle // 90 % 4])\n", "import sys\n\ndef hack(n):\n\treturn [1, 1, 0, 1, 0, 0, 1][n % 7]\n\ndef rot(m):\n\treturn list(zip(*m[::-1]))\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nmat = []\nfor i in range(1, n + 1):\n\tmat.append([hack((i * j) ** 2) for j in range(1, n + 1)])\ndiff90 = 0\nr = rot(mat)\nfor i in range(n):\n\tfor j in range(n):\n\t\tif mat[i][j] != r[i][j]:\n\t\t\tdiff90 += 1\ndiff180 = 0\nr = rot(r)\nfor i in range(n):\n\tfor j in range(n):\n\t\tif mat[i][j] != r[i][j]:\n\t\t\tdiff180 += 1\nfor a0 in range(q):\n\tangle = int(input().strip()) % 360 // 90\n\tif angle == 0:\n\t\tprint(0)\n\telif angle == 2:\n\t\tprint(diff180)\n\telse:\n\t\tprint(diff90)\n", "data = [1, 1, 0, 1, 0, 0, 1, 1]\nB = []\nC = [0, 32]\nD = [0, 32]\nE = [0, 48]\nF = [0, 54]\nG = [0, 88]\nfor i in range(0, 300):\n\tB.append(30 * i * i)\nt1 = 8\nt2 = 22\nfor i in range(2, 300):\n\tC.append(B[i] - t1)\n\tt1 += t2\n\tt2 += 12\nt1 = 6\nt2 = 10\nfor i in range(2, 300):\n\tD.append(C[i] - t1)\n\tt1 += t2\n\tt2 += 4\nt1 = 28\nfor i in range(2, 300):\n\tE.append(D[i] + t1)\n\tt1 += 12\nt1 = 16\nt2 = 14\nfor i in range(2, 300):\n\tF.append(E[i] + t1)\n\tt1 += t2\n\tt2 += 4\nt1 = 72\nt2 = 50\nfor i in range(2, 300):\n\tG.append(F[i] + t1)\n\tt1 += t2\n\tt2 += 12\n\ndef hack(i):\n\treturn data[i % 7]\n\ndef calculate1(n):\n\tif n == 1:\n\t\treturn 0\n\tif n == 2:\n\t\treturn 2\n\tif n == 3:\n\t\treturn 4\n\tif n == 4:\n\t\treturn 10\n\tif n == 5:\n\t\treturn 14\n\tn += 1\n\tx = n // 7\n\ty = n % 7\n\t(b, c, d, e, f, g) = (0, 0, 0, 0, 0, 0)\n\tif y == 0:\n\t\treturn 0\n\tb = 24 * x * x\n\tc = b + x * 4\n\td = c + 2 + x * 12\n\te = d + 2 + x * 4\n\tf = e + 6 + x * 10\n\tg = f + 4 + x * 8\n\tif y == 1:\n\t\treturn b\n\tif y == 2:\n\t\treturn c\n\tif y == 3:\n\t\treturn d\n\tif y == 4:\n\t\treturn e\n\tif y == 5:\n\t\treturn f\n\tif y == 6:\n\t\treturn g\n\ndef calculate2(n):\n\tans = [0, 0, 2, 6, 6, 14, 0, 30, 32, 32, 48, 54, 88]\n\tif n <= 12:\n\t\treturn ans[n]\n\tn += 1\n\tx = n // 7\n\ty = n % 7\n\tif y == 0:\n\t\treturn 0\n\tif y == 1:\n\t\treturn B[x]\n\tif y == 2:\n\t\treturn C[x]\n\tif y == 3:\n\t\treturn D[x]\n\tif y == 4:\n\t\treturn E[x]\n\tif y == 5:\n\t\treturn F[x]\n\tif y == 6:\n\t\treturn G[x]\n\ndef calculate22(n):\n\tcnt = 0\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tif hack(((n - i) * (n - j)) ** 2) != hack(((j + 1) * (i + 1)) ** 2):\n\t\t\t\tcnt += 1\n\treturn cnt\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tangle = angle % 360\n\tif angle == 0:\n\t\tprint(0)\n\telif angle == 90:\n\t\tprint(calculate1(n))\n\telif angle == 180:\n\t\tprint(calculate2(n))\n\telif angle == 270:\n\t\tprint(calculate1(n))\n", "import sys\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\narr = []\narrd = []\nh = [0, 0, 0, 0, 1, 1, 1]\na = []\nfor x in range(n):\n\ta.append([])\n\tfor y in range(n):\n\t\tif h[((x + 1) * (y + 1) - 2) % 7] == 1:\n\t\t\ta[x].append(1)\n\t\telse:\n\t\t\ta[x].append(0)\nc = {}\nc90 = 0\nc180 = 0\nfor x in range(n):\n\tfor y in range(n):\n\t\tif a[x][y] + a[x][n - 1 - y] == 1:\n\t\t\tc90 = c90 + 1\n\t\tif a[x][y] + a[n - x - 1][n - y - 1] == 1:\n\t\t\tc180 = c180 + 1\nc[90] = c90\nc[270] = c90\nc[180] = c180\nc[0] = 0\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tprint(c[angle % 360])\n", "import sys\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nperiod = [1, 0, 1, 0, 0, 1, 1]\nblock = [[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]]\n\ndef hackonacci_parity_bit(n):\n\tn = (n - 1) % 7\n\treturn period[n]\n\ndef hackonacci_matrix(n):\n\tmatrix = [[None] * n for _ in range(n)]\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tmatrix[i][j] = matrix[j][i] = hackonacci_parity_bit(((i + 1) * (j + 1)) ** 2)\n\treturn matrix\n\ndef compare1(mat, n):\n\ttotal = 0\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\ttotal += mat[i][j] != mat[n - 1 - j][i]\n\treturn total\n\ndef compare2(mat, n):\n\ttotal = 0\n\tfor i in range(0, n):\n\t\tfor j in range(i + 1, n):\n\t\t\ttotal += mat[i][j] != mat[n - 1 - i][n - 1 - j]\n\ttotal *= 2\n\tfor i in range(n):\n\t\ttotal += mat[i][i] != mat[n - 1 - i][n - 1 - i]\n\treturn total\n\ndef compare3(mat, n):\n\ttotal = 0\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\ttotal += mat[i][j] != mat[j][n - 1 - i]\n\treturn total\nmat = hackonacci_matrix(n)\nlst = [0, compare1(mat, n), compare2(mat, n), compare3(mat, n)]\nfor _ in range(q):\n\tangle = int(input().strip()) // 90 % 4\n\tprint(lst[angle])\n", "import sys\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\ntemp = [1, 0, 0, 1, 1, 1, 0]\nmatrix = [[-1] * n for t in range(n)]\nfor i in range(n):\n\tfor j in range(n):\n\t\tx = ((i + 1) * (j + 1)) ** 2\n\t\tif x == 1:\n\t\t\tmatrix[i][j] = 1\n\t\telif x == 2:\n\t\t\tmatrix[i][j] = 0\n\t\telse:\n\t\t\tmatrix[i][j] = temp[(x - 2 - 1) % 7]\ntemp1 = 0\ntemp2 = 0\ntemp3 = 0\nfor i in range(n):\n\tfor j in range(n):\n\t\tif matrix[i][j] != matrix[n - j - 1][i]:\n\t\t\ttemp1 += 1\n\t\tif matrix[i][j] != matrix[n - i - 1][n - j - 1]:\n\t\t\ttemp2 += 1\n\t\tif matrix[i][j] != matrix[j][n - i - 1]:\n\t\t\ttemp3 += 1\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tangle = angle % 360\n\tif angle == 90:\n\t\tprint(temp1)\n\telif angle == 180:\n\t\tprint(temp2)\n\telif angle == 270:\n\t\tprint(temp3)\n\telse:\n\t\tprint(0)\n", "import sys\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nh = {0: 1, 1: 1, 2: 0, 3: 1, 4: 0, 5: 0, 6: 1}\nm = [[h[((i + 1) * (j + 1)) ** 2 % 7] for i in range(n)] for j in range(n)]\nr = {}\nr[0] = 0\nr[90] = sum([sum([int(m[i][j] != m[n - j - 1][i]) for i in range(n)]) for j in range(n)])\nr[180] = sum([sum([int(m[i][j] != m[n - i - 1][n - j - 1]) for i in range(n)]) for j in range(n)])\nr[270] = r[90]\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tprint(r[angle % 360])\n", "import sys\n\ndef hackonacci(n):\n\tseq = [1, 0, 1, 0, 0, 1, 1]\n\treturn seq[(n - 1) % 7]\n\ndef matching(n, angle, x, y):\n\ttemp = 0\n\tfor i in range(1, y + 1):\n\t\tfor j in range(1, x + 1):\n\t\t\told = hackonacci((i * j) ** 2)\n\t\t\tif angle == 0:\n\t\t\t\tpair = (i, j)\n\t\t\telif angle == 90:\n\t\t\t\tpair = (n - j + 1, i)\n\t\t\telif angle == 180:\n\t\t\t\tpair = (n - i + 1, n - j + 1)\n\t\t\telif angle == 270:\n\t\t\t\tpair = (j, n - i + 1)\n\t\t\tnew = hackonacci((pair[0] * pair[1]) ** 2)\n\t\t\tif old != new:\n\t\t\t\ttemp += 1\n\treturn temp\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tangle = angle // 90 % 4 * 90\n\tcount = 0\n\ta = n // 7\n\tif a >= 1:\n\t\tcount += matching(n, angle, 7, 7) * a * a\n\tif a >= 1 and n % 7 != 0:\n\t\tcount += matching(n, angle, n % 7, 7) * a\n\t\tcount += matching(n, angle, 7, n % 7) * a\n\tif n % 7 != 0:\n\t\tcount += matching(n, angle, n % 7, n % 7)\n\tprint(count)\n", "import sys\nxx = [1, 1, 1, 0, 1, 0, 0]\n\ndef gm(size):\n\tx = [[0 for col in range(size)] for row in range(size)]\n\tfor i in range(size):\n\t\tfor j in range(size):\n\t\t\tn = ((i + 1) * (j + 1)) ** 2\n\t\t\tif n > 5:\n\t\t\t\tn = xx[(n - 6) % 7]\n\t\t\tx[i][j] = 'X' if n % 2 == 0 else 'Y'\n\treturn x\n\ndef rotated90(arr, i, j, l):\n\treturn arr[l - 1 - j][i]\n\ndef rotated180(arr, i, j, l):\n\treturn arr[l - 1 - i][l - 1 - j]\n\ndef rotated270(arr, i, j, l):\n\treturn arr[j][l - 1 - i]\nresults = {}\n\ndef count(arr, degree):\n\tresult = 0\n\tl = len(arr)\n\tif degree % 360 == 0:\n\t\treturn 0\n\telif (degree - 270) % 360 == 0:\n\t\tkey = 270\n\t\tfunc = rotated270\n\telif (degree - 180) % 360 == 0:\n\t\tkey = 180\n\t\tfunc = rotated180\n\telse:\n\t\tkey = 90\n\t\tfunc = rotated90\n\tif key in results:\n\t\treturn results[key]\n\tfor i in range(l):\n\t\tfor j in range(l):\n\t\t\targs = (arr, i, j, l)\n\t\t\tif arr[i][j] != func(*args):\n\t\t\t\tresult += 1\n\tresults[key] = result\n\treturn result\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nmatrix = gm(n)\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tprint(count(matrix, angle))\n", "def get_char(n):\n\tl = ['X', 'Y', 'X', 'X', 'Y', 'Y', 'Y']\n\treturn l[n % 7 - 2] if n != 1 else 'Y'\n\ndef get_diff_case(angle):\n\treturn angle % 360 // 90\n\ndef calc_diff(mx1, mx2, n):\n\tcount = 0\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tif mx1[i][j] != mx2[i][j]:\n\t\t\t\tcount += 1\n\treturn count\n(n, q) = map(int, input().split())\nmx_0 = [[get_char((i * j) ** 2) for j in range(1, n + 1)] for i in range(1, n + 1)]\nmx_1 = list(zip(*mx_0[::-1]))\nmx_2 = list(zip(*mx_1[::-1]))\nmx_3 = list(zip(*mx_2[::-1]))\ndiff_cases = [0, calc_diff(mx_0, mx_1, n), calc_diff(mx_0, mx_2, n), calc_diff(mx_0, mx_3, n)]\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tprint(diff_cases[get_diff_case(angle)])\n", "import sys\nimport math\npattern = [[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]]\n\ndef h(i, j):\n\treturn pattern[i % 7][j % 7]\n\ndef h_rotate(i, j, n, r):\n\tif r == 90:\n\t\t(i, j) = (n - j - 1, i)\n\telif r == 180:\n\t\t(i, j) = (n - j - 1, n - i - 1)\n\telif r == 270:\n\t\t(i, j) = (j, n - i - 1)\n\treturn h(i, j)\n\ndef query(n, q):\n\td = 0\n\tq = q % 360\n\tfor i in range(0, n):\n\t\tfor j in range(0, n):\n\t\t\tif h(i, j) != h_rotate(i, j, n, q):\n\t\t\t\td += 1\n\treturn d\ncache = [0, -1, -1, -1]\n\ndef query_cache(n, q):\n\tqc = int(q / 90) % 4\n\tif cache[qc] < 0:\n\t\tcache[qc] = query(n, q)\n\treturn cache[qc]\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tprint(query_cache(n, angle))\n", "import sys\nmaxn = 2009\nanotherArr = [0 for i in range(9)]\n(anotherArr[1], anotherArr[2], anotherArr[3]) = (1, 0, 1)\nfor i in range(4, 9):\n\tif anotherArr[i - 1] + anotherArr[i - 3] == 1:\n\t\tanotherArr[i] = 1\n\telse:\n\t\tanotherArr[i] = 0\narr0 = [[0 for x in range(maxn)] for y in range(maxn)]\narr90 = [[0 for x in range(maxn)] for y in range(maxn)]\narr180 = [[0 for x in range(maxn)] for y in range(maxn)]\narr270 = [[0 for x in range(maxn)] for y in range(maxn)]\n\ndef iterationDecider(start, end):\n\tif start < end:\n\t\treturn 1\n\telse:\n\t\treturn -1\n\ndef initialization(arr, L, R, T, B):\n\trowIterator = iterationDecider(L, R)\n\tcolIterator = iterationDecider(T, B)\n\tfor i in range(L, R, rowIterator):\n\t\tfor j in range(T, B, colIterator):\n\t\t\ttemp = ((i * j) ** 2 - 1) % 7\n\t\t\tif temp == 0:\n\t\t\t\ttemp = 7\n\t\t\ttemp += 1\n\t\t\tif anotherArr[temp] == 1:\n\t\t\t\tarr[i][j] = 1\n\t\t\telse:\n\t\t\t\tarr[i][j] = 0\n\ndef initialization_(arr, L, R, T, B):\n\trowIterator = iterationDecider(L, R)\n\tcolIterator = iterationDecider(T, B)\n\t(x, y) = (1, 1)\n\tfor i in range(L, R, rowIterator):\n\t\ty = 1\n\t\tfor j in range(T, B, colIterator):\n\t\t\tarr[x][y] = arr0[i][j]\n\t\t\ty += 1\n\t\tx += 1\n\ndef initialization__(arr, L, R, T, B):\n\trowIterator = iterationDecider(L, R)\n\tcolIterator = iterationDecider(T, B)\n\t(x, y) = (1, 1)\n\tfor i in range(L, R, rowIterator):\n\t\ty = 1\n\t\tfor j in range(T, B, colIterator):\n\t\t\tarr[x][y] = arr0[j][i]\n\t\t\ty += 1\n\t\tx += 1\n\ndef compareArr(arr1, arr2, n):\n\tdifferentCells = 0\n\tfor i in range(1, n, 1):\n\t\tfor j in range(1, n, 1):\n\t\t\tif arr1[i][j] == arr2[i][j]:\n\t\t\t\tdifferentCells += 0\n\t\t\telse:\n\t\t\t\tdifferentCells += 1\n\treturn differentCells\nsolutionDict = {}\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\ninitialization(arr0, 1, n + 1, 1, n + 1)\ninitialization__(arr90, 1, n + 1, n, 0)\ninitialization_(arr180, n, 0, n, 0)\ninitialization__(arr270, n, 0, 1, n + 1)\nsolutionDict[0] = compareArr(arr0, arr0, n + 1)\nsolutionDict[90] = compareArr(arr0, arr90, n + 1)\nsolutionDict[180] = compareArr(arr0, arr180, n + 1)\nsolutionDict[270] = compareArr(arr0, arr270, n + 1)\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tangle %= 360\n\tprint(solutionDict[angle])\n", "import sys, time\nfrom itertools import *\n\ndef store_differences(matrix, matrices):\n\tdiff = {}\n\tfor (angle, rotated) in matrices.items():\n\t\tcount = 0\n\t\tfor (a, b) in zip(matrix, rotated):\n\t\t\tfor (c, d) in zip(a, b):\n\t\t\t\tif c != d:\n\t\t\t\t\tcount += 1\n\t\tdiff[angle] = count\n\treturn diff\n\ndef main():\n\t(n, q) = input().strip().split(' ')\n\t(n, q) = [int(n), int(q)]\n\td = {0: 'Y', 1: 'Y', 2: 'X', 3: 'Y', 4: 'X', 5: 'X', 6: 'Y'}\n\tmatrix = []\n\tfor i in range(1, n + 1):\n\t\tt = [d[(i * j) ** 2 % 7] for j in range(1, n + 1)]\n\t\tmatrix.append(t)\n\trotated_90 = list(zip(*matrix[::-1]))\n\trotated_180 = list(zip(*rotated_90[::-1]))\n\trotated_270 = list(zip(*rotated_180[::-1]))\n\tmatrices = {0: matrix, 90: rotated_90, 180: rotated_180, 270: rotated_270}\n\tdiff = store_differences(matrix, matrices)\n\tfor a0 in range(q):\n\t\tangle = int(input().strip()) % 360\n\t\tprint(diff[angle])\nmain()\n", "import sys\n\ndef cell_value(n):\n\tn %= 7\n\tif n == 2 or n == 4 or n == 5:\n\t\treturn 1\n\telse:\n\t\treturn 0\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nm = []\nfor r in range(1, n + 1):\n\tt = []\n\tfor c in range(1, n + 1):\n\t\tt.append(cell_value((r * c) ** 2))\n\tm.append(t)\nres = [0, 0, 0, 0]\n\ndef rotate_cell(r, c):\n\tr -= 1\n\tc -= 1\n\tnew_r = r\n\tnew_c = c\n\tfor i in range(1, 4):\n\t\ttemp = new_c\n\t\tnew_c = n - new_r - 1\n\t\tnew_r = temp\n\t\tif m[r][c] != m[new_r][new_c]:\n\t\t\tres[i] += 1\n\treturn\nfor r in range(1, n + 1):\n\tfor c in range(1, n + 1):\n\t\trotate_cell(r, c)\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tangle %= 360\n\tangle //= 90\n\tprint(res[angle])\n", "import sys\nfrom itertools import chain\nhackonaccis = [1, 2, 3]\n\ndef hackonacci(n):\n\tl = len(hackonaccis)\n\tif l >= n:\n\t\treturn hackonaccis[n - 1]\n\telse:\n\t\tfor i in range(n - l):\n\t\t\thackonaccis.append(hackonaccis[-1] + 2 * hackonaccis[-2] + 3 * hackonaccis[-3])\n\t\treturn hackonaccis[n - 1]\nHACKONACCI_MOD_2_PATTERN = [1, 1, 0, 1, 0, 0, 1]\nHACKONACCI_PATTERN_LENGTH = len(HACKONACCI_MOD_2_PATTERN)\n\ndef hackonacci_mod_2(n):\n\treturn HACKONACCI_MOD_2_PATTERN[n % HACKONACCI_PATTERN_LENGTH]\nHACKONACCI_SQUARED_MOD_2_PATTERN = [1, 1, 0, 0, 0, 0, 1]\nHACKONACCI_SQUARED_PATTERN_LENGTH = len(HACKONACCI_MOD_2_PATTERN)\n\ndef hackonacci_squared_mod_2(n):\n\treturn HACKONACCI_SQUARED_MOD_2_PATTERN[n % HACKONACCI_SQUARED_PATTERN_LENGTH]\n\ndef hackonacci_matrix(n):\n\tmatrix = []\n\trow = None\n\tfor i in range(1, n + 1):\n\t\trow = []\n\t\tfor j in range(1, n + 1):\n\t\t\trow.append('X' if hackonacci_squared_mod_2(i * j) == 0 else 'Y')\n\t\tmatrix.append(row)\n\treturn matrix\n\ndef num_rotation_differences(n, angle):\n\tif n % 7 == 6:\n\t\treturn 0\n\tq = n // 14\n\tr = n % 14\n\tn_r = small_num_rotation_differences(r, angle)\n\tn_q = small_corners_rotation_differences(r, angle)\n\treturn n_r + n_q * q ** 2 + q * (small_num_rotation_differences(r + 14, angle) - n_q - n_r)\n\ndef small_corners_rotation_differences(r, angle):\n\n\tdef el_at(i, j):\n\t\treturn hackonacci_squared_mod_2((i + 1) * (j + 1))\n\tn = r + 14\n\tangle %= 360\n\tdifferences = 0\n\tcentre = (n - 1) / 2\n\tif angle == 0:\n\t\tpass\n\telif angle == 90:\n\t\tfor i in chain(range(0, 7), range(7 + r, n)):\n\t\t\tfor j in chain(range(0, 7), range(7 + r, n)):\n\t\t\t\tif el_at(i, j) != el_at(j, int(2 * centre) - i):\n\t\t\t\t\tdifferences += 1\n\telif angle == 180:\n\t\tfor i in chain(range(0, 7), range(7 + r, n)):\n\t\t\tfor j in chain(range(0, 7), range(7 + r, n)):\n\t\t\t\tif el_at(i, j) != el_at(int(2 * centre) - i, int(2 * centre) - j):\n\t\t\t\t\tdifferences += 1\n\telif angle == 270:\n\t\tfor i in chain(range(0, 7), range(7 + r, n)):\n\t\t\tfor j in chain(range(0, 7), range(7 + r, n)):\n\t\t\t\tif el_at(i, j) != el_at(int(2 * centre) - j, i):\n\t\t\t\t\tdifferences += 1\n\telse:\n\t\traise ValueError('Angle must be a multiple of 90!')\n\treturn differences\n\ndef small_num_rotation_differences(n, angle):\n\n\tdef el_at(i, j):\n\t\treturn hackonacci_squared_mod_2((i + 1) * (j + 1))\n\tangle %= 360\n\tdifferences = 0\n\tcentre = (n - 1) / 2\n\tif angle == 0:\n\t\tpass\n\telif angle == 90:\n\t\tfor i in range(n):\n\t\t\tfor j in range(n):\n\t\t\t\tif el_at(i, j) != el_at(j, int(2 * centre) - i):\n\t\t\t\t\tdifferences += 1\n\telif angle == 180:\n\t\tfor i in range(n):\n\t\t\tfor j in range(n):\n\t\t\t\tif el_at(i, j) != el_at(int(2 * centre) - i, int(2 * centre) - j):\n\t\t\t\t\tdifferences += 1\n\telif angle == 270:\n\t\tfor i in range(n):\n\t\t\tfor j in range(n):\n\t\t\t\tif el_at(i, j) != el_at(int(2 * centre) - j, i):\n\t\t\t\t\tdifferences += 1\n\telse:\n\t\traise ValueError('Angle must be a multiple of 90!')\n\treturn differences\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tprint(num_rotation_differences(n, angle))\n", "import sys\n\ndef calc_diff(matr, rot):\n\tn = len(matr)\n\tcount = 0\n\trot_modulo = rot % 360\n\tif rot_modulo == 0:\n\t\treturn 0\n\tif rot_modulo == 90:\n\t\trotated = rot90(matr)\n\tif rot_modulo == 180:\n\t\trotated = rot180(matr)\n\tif rot_modulo == 270:\n\t\trotated = rot270(matr)\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tif matr[i][j] != rotated.__next__():\n\t\t\t\tcount += 1\n\treturn count\n\ndef rot90(matr):\n\tmax_n = len(matr) - 1\n\tcol = max_n\n\trow = 0\n\twhile True:\n\t\tyield matr[row][col]\n\t\trow += 1\n\t\tif row > max_n:\n\t\t\t(row, col) = (0, col - 1)\n\ndef rot180(matr):\n\tmax_n = len(matr) - 1\n\t(row, col) = (max_n, max_n)\n\twhile True:\n\t\tyield matr[row][col]\n\t\tcol -= 1\n\t\tif col < 0:\n\t\t\t(row, col) = (row - 1, max_n)\n\ndef rot270(matr):\n\tmax_n = len(matr) - 1\n\t(row, col) = (max_n, 0)\n\twhile True:\n\t\tyield matr[row][col]\n\t\trow -= 1\n\t\tif row < 0:\n\t\t\t(row, col) = (max_n, col + 1)\n\ndef create_counts(parities, n):\n\tcounts = [0, 0]\n\n\tdef coord_to_val(i, j):\n\t\tvalue1 = (i + 1) % 7\n\t\tvalue2 = (j + 1) % 7\n\t\tmulti = value1 * value2 % 7\n\t\treturn multi ** 2 % 7\n\tfor i in range(n // 2):\n\t\tfor j in range(n // 2):\n\t\t\tcur_p = parities[coord_to_val(i, j)]\n\t\t\tcur_90 = parities[coord_to_val(i, n - j - 1)]\n\t\t\tcur_180 = parities[coord_to_val(n - i - 1, n - j - 1)]\n\t\t\tcur_270 = parities[coord_to_val(n - i - 1, j)]\n\t\t\tif cur_p != cur_90:\n\t\t\t\tcounts[0] += 1\n\t\t\tif cur_p != cur_180:\n\t\t\t\tcounts[1] += 2\n\t\t\tif cur_p != cur_270:\n\t\t\t\tcounts[0] += 1\n\t\t\tif cur_90 != cur_180:\n\t\t\t\tcounts[0] += 1\n\t\t\tif cur_90 != cur_270:\n\t\t\t\tcounts[1] += 2\n\t\t\tif cur_180 != cur_270:\n\t\t\t\tcounts[0] += 1\n\tif n % 2 == 1:\n\t\tmid = n // 2\n\t\tfor i in range(n // 2):\n\t\t\tcur_p = (i, mid)\n\t\t\tcur_90 = (mid, n - i - 1)\n\t\t\tcur_180 = (n - i - 1, mid)\n\t\t\tcur_270 = (mid, i)\n\t\t\tcur_p = parities[coord_to_val(*cur_p)]\n\t\t\tcur_90 = parities[coord_to_val(*cur_90)]\n\t\t\tcur_180 = parities[coord_to_val(*cur_180)]\n\t\t\tcur_270 = parities[coord_to_val(*cur_270)]\n\t\t\tif cur_p != cur_90:\n\t\t\t\tcounts[0] += 1\n\t\t\tif cur_p != cur_180:\n\t\t\t\tcounts[1] += 2\n\t\t\tif cur_p != cur_270:\n\t\t\t\tcounts[0] += 1\n\t\t\tif cur_90 != cur_180:\n\t\t\t\tcounts[0] += 1\n\t\t\tif cur_90 != cur_270:\n\t\t\t\tcounts[1] += 2\n\t\t\tif cur_180 != cur_270:\n\t\t\t\tcounts[0] += 1\n\treturn counts\n\ndef main(inp=sys.stdin):\n\t(n, q) = [int(x) for x in inp.readline().strip().split()]\n\tparities = [1, 1, 0, 1, 0, 0, 1]\n\tcounts = create_counts(parities, n)\n\tfor query in range(q):\n\t\trota = int(inp.readline().strip()) % 360\n\t\tif rota == 180:\n\t\t\tprint(counts[1])\n\t\telse:\n\t\t\tprint(counts[0])\n\ndef main2(inp=sys.stdin):\n\t(n, q) = [int(x) for x in inp.readline().strip().split()]\n\tparities = [1, 1, 0, 1, 0, 0, 1]\n\tcur_mat = [[None for i in range(n)] for j in range(n)]\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tvalue = (i + 1) * (j + 1)\n\t\t\tparity = parities[value ** 2 % 7]\n\t\t\tcur_mat[i][j] = parity\n\tanswers = {0: calc_diff(cur_mat, 0), 90: calc_diff(cur_mat, 90), 180: calc_diff(cur_mat, 180), 270: calc_diff(cur_mat, 270)}\n\tfor query in range(q):\n\t\trota = int(inp.readline().strip()) % 360\n\t\tprint(answers[rota])\nmain2()\n", "import sys\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nhaconacci_table = {1: 'Y', 2: 'X', 3: 'Y', 4: 'X', 5: 'X', 6: 'Y', 7: 'Y'}\n\ndef get_XY(n):\n\treturn haconacci_table[(n - 1) % 7 + 1]\n\ndef _get_iterator(n, angle):\n\tif angle == 0:\n\t\taxis_i = range(1, n + 1)\n\t\taxis_j = range(1, n + 1)\n\telif angle == 90:\n\t\taxis_i = range(1, n + 1)\n\t\taxis_j = range(n, 0, -1)\n\telif angle == 180:\n\t\taxis_i = range(n, 0, -1)\n\t\taxis_j = range(n, 0, -1)\n\telif angle == 270:\n\t\taxis_i = range(n, 0, -1)\n\t\taxis_j = range(1, n + 1)\n\treturn (axis_i, axis_j)\n\ndef build_table(n):\n\ttable = [[None for _ in range(n + 1)] for _ in range(n + 1)]\n\tfor i in range(1, n + 1):\n\t\tfor j in range(1, n + 1):\n\t\t\ttable[i][j] = get_XY((i * j) ** 2)\n\treturn table\n\ndef diff_table(t, a1, a2, n):\n\tdiff = 0\n\t(iter_i1, iter_j1) = _get_iterator(n, a1)\n\t(iter_i2, iter_j2) = _get_iterator(n, a2)\n\tfor (i1, i2) in zip(iter_i1, iter_i2):\n\t\tfor (j1, j2) in zip(iter_j1, iter_j2):\n\t\t\tif t[i1][j1] != t[i2][j2]:\n\t\t\t\tdiff += 1\n\treturn diff\ntable = build_table(n)\ndiff_result = [0]\ndiff_result.append(diff_table(table, 0, 90, n))\ndiff_result.append(diff_table(table, 0, 180, n))\ndiff_result.append(diff_table(table, 0, 270, n))\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tprint(diff_result[angle % 360 // 90])\n", "import sys\ntest = [False, True, False, True, True, False, False]\n\ndef par(n):\n\treturn test[(n - 1) % 7]\n\ndef main(argv=sys.argv):\n\t(n, q) = input().strip().split(' ')\n\t(n, q) = [int(n), int(q)]\n\tmat = [[par((i + 1) * (i + 1) * (j + 1) * (j + 1)) for i in range(n)] for j in range(n)]\n\tmat90 = list(zip(*mat[::-1]))\n\tmat180 = list(zip(*mat90[::-1]))\n\tmat270 = list(zip(*mat))[::-1]\n\tndiff90 = 0\n\tndiff180 = 0\n\tndiff270 = 0\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tif mat[i][j] != mat90[i][j]:\n\t\t\t\tndiff90 = ndiff90 + 1\n\t\t\tif mat[i][j] != mat180[i][j]:\n\t\t\t\tndiff180 = ndiff180 + 1\n\t\t\tif mat[i][j] != mat270[i][j]:\n\t\t\t\tndiff270 = ndiff270 + 1\n\tfor a0 in range(q):\n\t\tangle = int(input().strip())\n\t\tangle = angle % 360\n\t\tndiff = 0\n\t\tif angle == 0:\n\t\t\tndiff = 0\n\t\telif angle == 90:\n\t\t\tndiff = ndiff90\n\t\telif angle == 180:\n\t\t\tndiff = ndiff180\n\t\telif angle == 270:\n\t\t\tndiff = ndiff270\n\t\tprint(ndiff)\n\treturn 0\nsys.exit(main())\n", "import sys\n(mat_dim, q) = input().strip().split(' ')\n(mat_dim, q) = [int(mat_dim), int(q)]\nx_y_pattern = {0: 'Y', 1: 'Y', 2: 'X', 3: 'Y', 4: 'X', 5: 'X', 6: 'Y'}\nhack_table = []\nfor row in range(1, mat_dim + 1):\n\tcurrent_row = []\n\tfor col in range(1, mat_dim + 1):\n\t\tcurrent_row.append(x_y_pattern[(row * col) ** 2 % 7])\n\thack_table.append(current_row)\nrotation_pattern = {}\nchanged = 0\nfor row in range(mat_dim):\n\tchanged += sum([el1 != el2 for (el1, el2) in zip(hack_table[row], hack_table[:][row][::-1])])\nrotation_pattern[90] = changed\nchanged = 0\nfor row in range(mat_dim):\n\tchanged += sum([el1 != el2 for (el1, el2) in zip(hack_table[row], hack_table[mat_dim - row - 1][::-1])])\nrotation_pattern[180] = changed\nchanged = 0\nfor row in range(mat_dim):\n\tchanged += sum([el1 != el2 for (el1, el2) in zip(hack_table[row], hack_table[:][mat_dim - row - 1])])\nrotation_pattern[270] = changed\nrotation_pattern[0] = 0\nfor angle in range(q):\n\tangle = int(input().strip())\n\tangle = angle % 360\n\tprint(rotation_pattern[angle])\n", "(n, q) = [int(x) for x in input().split()]\nh = ['y', 'y', 'n', 'y', 'n', 'n', 'y']\n(r90, r180) = (0, 0)\nfor i in range(1, 1 + n):\n\tii = i * i\n\ti2 = n + 1 - i\n\tii2 = i2 * i2 % 7\n\tfor j in range(1, 1 + n):\n\t\tj2 = n + 1 - j\n\t\tval = h[ii * j * j % 7]\n\t\tif val != h[ii2 * j * j % 7]:\n\t\t\tr90 += 1\n\t\tif val != h[ii2 * j2 * j2 % 7]:\n\t\t\tr180 += 1\nanswers = [0] * 300\nanswers[90] = r90\nanswers[180] = r180\nanswers[270] = r90\nfor _ in range(q):\n\tprint(answers[int(input()) % 360])\n", "import sys\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\na = [0, 0, 1, 0, 1, 1, 0]\nc = 0\nfor i in range(n):\n\tfor j in range(n):\n\t\tt1 = ((i + 1) * (j + 1)) ** 2 % 7\n\t\tt2 = ((j + 1) * (n - (i + 1) + 1)) ** 2 % 7\n\t\tif a[t1] != a[t2]:\n\t\t\tc = c + 1\nb = []\nb.append(0)\nb.append(c)\nd = c\nc = 0\nfor i in range(n):\n\tfor j in range(n):\n\t\tt1 = ((i + 1) * (j + 1)) ** 2 % 7\n\t\tt2 = ((n - i) * (n - (j + 1) + 1)) ** 2 % 7\n\t\tif a[t1] != a[t2]:\n\t\t\tc = c + 1\nb.append(c)\nb.append(d)\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tangle = angle % 360\n\tc = int(angle / 90)\n\tprint(b[c])\n", "hack = [1, 0, 0, 1, 1, 1, 0]\n\ndef h(n):\n\tif n == 1:\n\t\treturn 1\n\tif n == 2:\n\t\treturn 0\n\treturn hack[(n - 3) % 7]\n\ndef rotate90(n):\n\tc = 0\n\tfor i in range(1, n + 1):\n\t\tfor j in range(1, n // 2 + 1):\n\t\t\tif h((i * j) ** 2) != h((i * (n + 1 - j)) ** 2):\n\t\t\t\tc += 2\n\treturn c\n\ndef rotate270(n):\n\tc = 0\n\tfor j in range(1, n + 1):\n\t\tfor i in range(1, n // 2 + 1):\n\t\t\tif h((i * j) ** 2) != h((j * (n + 1 - i)) ** 2):\n\t\t\t\tc += 2\n\treturn c\n\ndef rotate180(n):\n\tc = 0\n\tif n % 2 == 1:\n\t\tfor i in range(1, n + 1):\n\t\t\tif i == n // 2 + 1:\n\t\t\t\tfor j in range(1, n // 2 + 1):\n\t\t\t\t\tif h((i * j) ** 2) != h(((n + 1 - j) * i) ** 2):\n\t\t\t\t\t\tc += 2\n\t\t\t\tcontinue\n\t\t\tfor j in range(1, n // 2 + 1):\n\t\t\t\tif h((i * j) ** 2) != h(((n + 1 - j) * (n + 1 - i)) ** 2):\n\t\t\t\t\tc += 2\n\t\t\tj = n // 2 + 1\n\t\t\tif h((i * j) ** 2) != h((j * (n + 1 - i)) ** 2):\n\t\t\t\tc += 1\n\telse:\n\t\tfor i in range(1, n + 1):\n\t\t\tfor j in range(1, n // 2 + 1):\n\t\t\t\tif h((i * j) ** 2) != h(((n + 1 - j) * (n + 1 - i)) ** 2):\n\t\t\t\t\tc += 2\n\treturn c\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nd = {}\nd[0] = 0\nd[90] = rotate90(n)\nd[180] = rotate180(n)\nd[270] = rotate270(n)\nfor _ in range(q):\n\tangle = int(input().strip())\n\tangle %= 360\n\tprint(d[angle])\n", "import math\n\ndef calc_180(n):\n\tinitial = [0, 0, 1, 3, 3, 7, 0, 15, 16, 16, 24, 27, 44, 0]\n\tpattern = [15, 12, 11, 11, 12, 15]\n\tn += 1\n\tf = int(n % 7)\n\tif f == 0:\n\t\treturn 0\n\tf -= 1\n\tm = math.floor(n / 7)\n\tif m < 2:\n\t\treturn initial[7 * m + f] * 2\n\ttotal = m * (initial[f + 7] - initial[f] + (m - 1) * pattern[f]) + initial[f]\n\treturn int(total * 2)\n\ndef calc_90(n):\n\tinitial = [0, 0, 1, 2, 5, 7, 0]\n\tpattern = [5, 2, 6, 2, 5, 4]\n\tn += 1\n\tf = int(n % 7)\n\tif f == 0:\n\t\treturn 0\n\tm = math.floor(n / 7)\n\tif m < 1:\n\t\treturn initial[f - 1] * 2\n\ttotal = m * (initial[-2] + sum(pattern) * (m - 1) / 2)\n\tfor i in range(f):\n\t\ttotal += initial[i] - initial[i - 1] + m * pattern[i]\n\treturn int(total * 2)\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tangle = angle % 360\n\tif angle == 0:\n\t\tprint(0)\n\telif angle == 180:\n\t\tprint(calc_180(n))\n\telse:\n\t\tprint(calc_90(n))\n", "import sys\n\ndef par_hacko(n):\n\tpattern = [1, 0, 1, 0, 0, 1, 1]\n\tl = len(pattern)\n\treturn pattern[n % l - 1]\n\ndef hack_M(n):\n\tM = [[par_hacko((i * j) ** 2) for j in range(1, n + 1)] for i in range(1, n + 1)]\n\treturn M\n\ndef diff(M, r):\n\tn = len(M)\n\tif r == 1 or r == 3:\n\t\treturn sum([sum([1 if M[n - j - 1][i] != M[i][j] else 0 for j in range(n)]) for i in range(n)])\n\telif r == 2:\n\t\treturn 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)])\n\ndef answer(n, Q):\n\tM = hack_M(n)\n\tdiffs = [0, diff(M, 1), diff(M, 2), diff(M, 3)]\n\tQ = [q // 90 % 4 for q in Q]\n\treturn [diffs[q] for q in Q]\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nQ = []\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tQ.append(angle)\nA = answer(n, Q)\nfor a in A:\n\tprint(a)\n", "import sys\n\ndef hackonacci(n):\n\tif n <= 3:\n\t\treturn n\n\tif n in hack:\n\t\treturn hack[n]\n\th = (hackonacci(n - 1) + hackonacci(n - 3)) % 2\n\tif n < 10 ** 4:\n\t\thack[n] = h\n\treturn h\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nhack = {}\narr = []\nfor _ in range(n):\n\tarr.append(['Y'] * n)\nfor i in range(n):\n\tfor j in range(n):\n\t\tif ((i + 1) * (j + 1)) ** 2 == 2 or (((i + 1) * (j + 1)) ** 2 - 2) % 7 in [0, 3, 2]:\n\t\t\tarr[i][j] = 'X'\nsoln = {}\nfor a0 in range(q):\n\tangle = int(input().strip())\n\trotations = angle // 90 % 4\n\tif rotations in soln:\n\t\tprint(soln[rotations])\n\telse:\n\t\trotate = []\n\t\tfor i in range(n):\n\t\t\trotate.append(arr[i][:])\n\t\tfor i in range(rotations):\n\t\t\trotate = list(zip(*rotate[::-1]))\n\t\tchanges = 0\n\t\tfor i in range(n):\n\t\t\tfor j in range(n):\n\t\t\t\tif rotate[i][j] != arr[i][j]:\n\t\t\t\t\tchanges += 1\n\t\tprint(changes)\n\t\tsoln[rotations] = changes\n", "import sys\n\ndef rotate_matrix_indexes(matrix):\n\tn = len(matrix)\n\tnew_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)]\n\treturn new_matrix\n\ndef rotate_indexes(i, j, n, times=1):\n\tfor time in range(times):\n\t\tz = n - j - 1\n\t\tw = i\n\t\ti = z\n\t\tj = w\n\treturn (i, j)\n\ndef hackonacci(n):\n\tif n == 0:\n\t\treturn 0\n\tif n == 1:\n\t\treturn 1\n\thack = [0, 1, 0, 0, 1, 1, 1]\n\tpos = (n - 2) % 7\n\treturn hack[pos]\n\ndef create_matrix(n):\n\tmatrix = [[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)]\n\treturn matrix\n\ndef rotate_matrix(matrix, times):\n\tif not times:\n\t\treturn matrix\n\tnew_matrix = list(zip(*matrix[::-1]))\n\tfor rotation in range(times - 1):\n\t\tnew_matrix = list(zip(*new_matrix[::-1]))\n\treturn new_matrix\n\ndef count_differences(matrix1, matrix2):\n\tn = len(matrix1)\n\tdifferences = 0\n\tfor row in range(n):\n\t\tfor col in range(n):\n\t\t\tif matrix1[row][col] != matrix2[row][col]:\n\t\t\t\tdifferences += 1\n\treturn differences\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nmatrix = create_matrix(n)\ncached = {}\nfor a0 in range(q):\n\tangle = int(input().strip())\n\ttimes = angle % 360 // 90\n\tif times:\n\t\tif times == 3:\n\t\t\ttimes = 1\n\t\ttry:\n\t\t\tprint(cached[times])\n\t\texcept KeyError:\n\t\t\tnm = rotate_matrix(matrix, times)\n\t\t\tdifferences = count_differences(matrix, nm)\n\t\t\tcached[times] = differences\n\t\t\tprint(differences)\n\telse:\n\t\tprint(0)\n", "[n, q] = [int(x) for x in input().split()]\nquery = []\nfor i in range(0, q):\n\tquery.append(int(input()))\nquery = [int(x / 90) % 4 for x in query]\nrot = [0, 0, 0]\nrot_flag = [1, 0, 0]\nH = [0, 1, 0, 1, 1, 0, 0]\nA = []\nfor i in range(0, n):\n\tB = []\n\tfor j in range(0, n):\n\t\tB.append(H[(((i + 1) * (j + 1)) ** 2 - 1) % 7])\n\tA.append(B)\n\ndef r90():\n\trot_flag[1] = 1\n\tr = 0\n\tfor l in range(0, n):\n\t\tfor m in range(0, n):\n\t\t\tif A[l][m] != A[n - m - 1][l]:\n\t\t\t\tr += 1\n\trot[1] = r\n\ndef r180():\n\trot_flag[2] = 1\n\ts = 0\n\tfor l in range(0, n):\n\t\tfor m in range(0, n):\n\t\t\tif A[l][m] != A[n - l - 1][n - m - 1]:\n\t\t\t\ts += 1\n\trot[2] = s\nfor i in range(0, q):\n\tif query[i] == 0:\n\t\tprint(rot[0])\n\telif query[i] == 2:\n\t\tif rot_flag[2] == 0:\n\t\t\tr180()\n\t\tprint(rot[2])\n\telse:\n\t\tif rot_flag[1] == 0:\n\t\t\tr90()\n\t\tprint(rot[1])\n", "def rotate(m, d):\n\tfor __ in range(d):\n\t\tm = list(zip(*m[::-1]))\n\treturn m\n\ndef difference(x, y):\n\treturn sum([sum([x ^ y for (x, y) in zip(i, j)]) for (i, j) in zip(x, y)])\n\ndef gethackonacci():\n\th = [1, 2, 3]\n\tfor i in range(3, 21):\n\t\th.append(h[i - 1] + 2 * h[i - 2] + 3 * h[i - 3])\n\treturn [(0, 1)[i % 2 == 0] for i in h]\n\ndef getmatrix(n):\n\treturn [[h[(i * j) ** 2 % 21 - 1] for i in range(1, n + 1)] for j in range(1, n + 1)]\n\ndef solve(n, q):\n\tm = getmatrix(n)\n\trot = []\n\tfor __ in range(q):\n\t\trot.append(int(input()) // 90)\n\tfour_rotations = []\n\tfor i in range(1, 4):\n\t\tfour_rotations.append(difference(m, rotate(m, i)))\n\tfour_rotations.append(0)\n\tres = [str(four_rotations[r % 4 - 1]) for r in rot]\n\tprint('\\n'.join(res))\n(n, q) = map(int, input().split())\nh = gethackonacci()\nsolve(n, q)\n", "(n, t) = input().split()\n(n, t) = (int(n), int(t))\nq = []\nfor i in range(t):\n\tq.append(int(input()))\nans = [2]\nx = 1\nl = 1\nwhile l <= 4000000:\n\tif x == 1:\n\t\tans.append(1)\n\t\tans.append(1)\n\t\tans.append(1)\n\t\tans.append(1)\n\t\tx = 0\n\t\tl = l + 4\n\telse:\n\t\tans.append(2)\n\t\tans.append(2)\n\t\tans.append(2)\n\t\tx = 1\n\t\tl = l + 3\nrotations = [0, 0, 0, 0]\na = []\nb = []\nfor i in range(n):\n\ta.append([])\n\tfor j in range(n):\n\t\tc = int(i + 1)\n\t\td = int(j + 1)\n\t\tg = int(c * d)\n\t\ta[i].append(ans[g - 1])\nb = zip(*a[::-1])\nb = list(b)\ncount = 0\nfor i in range(n):\n\tfor j in range(n):\n\t\tif a[i][j] != b[i][j]:\n\t\t\tcount = count + 1\nrotations[1] = count\nb = zip(*b[::-1])\nb = list(b)\ncount = 0\nfor i in range(n):\n\tfor j in range(n):\n\t\tif a[i][j] != b[i][j]:\n\t\t\tcount = count + 1\nrotations[2] = count\nb = zip(*b[::-1])\nb = list(b)\ncount = 0\nfor i in range(n):\n\tfor j in range(n):\n\t\tif a[i][j] != b[i][j]:\n\t\t\tcount = count + 1\nrotations[3] = count\nfor i in range(t):\n\tx = int(q[i] / 90 % 4)\n\tprint(rotations[x])\n", "import sys\n\ndef hackonacci_num(n):\n\tlookup = (n - 3) % 7\n\thack_nums = {0: 1, 1: 1, 2: 0, 3: 1, 4: 0, 5: 0, 6: 1}\n\tans = hack_nums[lookup]\n\treturn ans\n\ndef hackonacci_mat(n):\n\tmat = []\n\tfor i in range(n):\n\t\tmat.append([])\n\t\tfor j in range(n):\n\t\t\tmat[i].append(0)\n\tfor i in range(n):\n\t\tfor j in range(i, n):\n\t\t\thack_num = hackonacci_num((i + 1) * (j + 1) * (i + 1) * (j + 1))\n\t\t\tmat[i][j] = hack_num\n\t\t\tmat[j][i] = hack_num\n\treturn mat\n\ndef mat_diff(mat, angle):\n\tdiff_sum = 0\n\tfor i in range(len(mat)):\n\t\tfor j in range(len(mat)):\n\t\t\tif angle == 180:\n\t\t\t\tdiff_sum += abs(mat[i][j] - mat[-i - 1][-j - 1])\n\t\t\telif angle == 90:\n\t\t\t\tdiff_sum += abs(mat[i][j] - mat[j][-i - 1])\n\t\t\telif angle == 270:\n\t\t\t\tdiff_sum += abs(mat[i][j] - mat[-j - 1][i])\n\treturn diff_sum\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\ntest_mat = hackonacci_mat(n)\ncalc_angles = {}\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tangle = angle % 360\n\tif angle in calc_angles:\n\t\tprint(calc_angles[angle])\n\telse:\n\t\tans = mat_diff(test_mat, angle)\n\t\tprint(ans)\n\t\tcalc_angles[angle] = ans\n", "import sys\n\ndef hackonacci(int1):\n\tdic = {}\n\t(h1, h2, h3) = (1, 2, 3)\n\tif int1 == 1:\n\t\tdic[int1] = h1\n\t\treturn dic\n\telif int1 == 2:\n\t\tdic[1] = 1\n\t\tdic[int1] = h2\n\t\treturn dic\n\telif int1 == 3:\n\t\t(dic[1], dic[2]) = (1, 2)\n\t\tdic[int1] = h3\n\t\treturn dic\n\t(dic[1], dic[2], dic[3]) = (1, 2, 3)\n\tfor i in range(4, int1 + 1):\n\t\th = (h1 + 2 * h2 + 3 * h3) % 10\n\t\tdic[i] = h\n\t\t(h1, h2, h3) = (h2, h3, h)\n\treturn dic\n\ndef difference(mlst, n, int2):\n\tif int2 == 1:\n\t\tcount = 0\n\t\tfor i in range(n):\n\t\t\tfor j in range(n):\n\t\t\t\tif mlst[i][j] != mlst[n - j - 1][i]:\n\t\t\t\t\tcount += 1\n\t\treturn count\n\telif int2 == 2:\n\t\tcount = 0\n\t\tfor i in range(n):\n\t\t\tfor j in range(n):\n\t\t\t\tif mlst[i][j] != mlst[n - i - 1][n - j - 1]:\n\t\t\t\t\tcount += 1\n\t\treturn count\n\telse:\n\t\tcount = 0\n\t\tfor i in range(n):\n\t\t\tfor j in range(n):\n\t\t\t\tif mlst[i][j] != mlst[j][n - i - 1]:\n\t\t\t\t\tcount += 1\n\t\treturn count\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nmtx = []\nfor i in range(n):\n\tmtx.append(list('O' * n))\nhack_dic = hackonacci(n * n)\nfor i in range(1, n + 1):\n\tfor j in range(i, n + 1):\n\t\tif (i * j - 3) % 7 == 0:\n\t\t\trem = (hack_dic[i * j] + 1) % 2\n\t\telse:\n\t\t\trem = hack_dic[i * j] % 2\n\t\tc = 'X' if rem == 0 else 'Y'\n\t\tif i != j:\n\t\t\tmtx[j - 1][i - 1] = c\n\t\tmtx[i - 1][j - 1] = c\ndic_q = {0: 0, 1: difference(mtx, n, 1), 2: difference(mtx, n, 2), 3: difference(mtx, n, 3)}\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tk = angle // 90 % 4\n\tprint(dic_q[k])\n", "import math\n\ndef rotate(X):\n\tl = [[X[j][i] for j in range(len(X) - 1, -1, -1)] for i in range(0, len(X))]\n\treturn l\n\ndef ro(l):\n\tA = rotate(l)\n\tB = rotate(A)\n\tC = rotate(B)\n\tt90 = 0\n\tt180 = 0\n\tt270 = 0\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tif A[i][j] != l[i][j]:\n\t\t\t\tt90 += 1\n\t\t\tif B[i][j] != l[i][j]:\n\t\t\t\tt180 += 1\n\t\t\tif C[i][j] != l[i][j]:\n\t\t\t\tt270 += 1\n\treturn (t90, t180)\nl = ['X    X', '  XX  ', ' X  X ', ' X  X ', '  XX  ', 'X    X']\nt = list(l)\n(n, k) = [int(x) for x in input().split()]\n(r, c) = (6, 6)\nif n > 6:\n\twhile c < n:\n\t\tif c + 7 < n:\n\t\t\tfor i in range(6):\n\t\t\t\tl[i] = l[i] + 'X' + t[i]\n\t\t\tc += 7\n\t\telse:\n\t\t\tfor i in range(6):\n\t\t\t\tl[i] = l[i] + 'X' + t[i][0:n - c - 1]\n\t\t\tc = n\n\twhile r < n:\n\t\tl.append('X' * c)\n\t\tif r + 7 < n:\n\t\t\tfor i in range(6):\n\t\t\t\tl.append(l[i])\n\t\telse:\n\t\t\tfor i in range(n - r - 1):\n\t\t\t\tl.append(l[i])\n\t\tr += 7\nelse:\n\tt = t[:n]\n\tfor i in range(len(t)):\n\t\tt[i] = t[i][:n]\n\tl = t\n(t9, t18) = ro(l)\nfor i in range(k):\n\tx = int(input()) % 360\n\tif x == 0:\n\t\tprint('0')\n\telif x == 90 or x == 270:\n\t\tprint(t9)\n\telse:\n\t\tprint(t18)\n", "import sys\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nv = [False, True, False, True, True, False, False]\ng = []\nfor i in range(n):\n\tg.append([])\n\tfor o in range(n):\n\t\tg[i].append(-1)\n\ndef gp(i, o):\n\tif g[i][o] == -1:\n\t\tg[i][o] = v[((i + 1) * (o + 1) * ((i + 1) * (o + 1)) - 1) % len(v)]\n\treturn g[i][o]\nangle90 = -1\nangle180 = -1\nangle270 = -1\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tdiff = 0\n\tangle = angle % 360\n\tif angle == 90:\n\t\tif angle90 == -1:\n\t\t\tfor i in range(n):\n\t\t\t\tfor o in range(n):\n\t\t\t\t\tif gp(i, o) != gp(n - i - 1, o):\n\t\t\t\t\t\tdiff += 1\n\t\t\tangle90 = diff\n\t\telse:\n\t\t\tdiff = angle90\n\telif angle == 180:\n\t\tif angle180 == -1:\n\t\t\tfor i in range(n):\n\t\t\t\tfor o in range(n):\n\t\t\t\t\tif gp(i, o) != gp(n - i - 1, n - o - 1):\n\t\t\t\t\t\tdiff += 1\n\t\t\tangle180 = diff\n\t\telse:\n\t\t\tdiff = angle180\n\telif angle == 270:\n\t\tif angle270 == -1:\n\t\t\tfor i in range(n):\n\t\t\t\tfor o in range(n):\n\t\t\t\t\tif gp(i, o) != gp(i, n - o - 1):\n\t\t\t\t\t\tdiff += 1\n\t\t\tangle270 = diff\n\t\telse:\n\t\t\tdiff = angle270\n\tprint(diff)\n", "(n, q) = map(int, input().split())\nm = [[i * i * j * j % 7 in [1, 3, 6, 0] for j in range(1, n + 1)] for i in range(1, n + 1)]\n(r, mr) = ([0], list(m))\nfor _ in range(3):\n\tmr = list(zip(*mr))[::-1]\n\tr.append(sum((m[i][j] != mr[i][j] for i in range(n) for j in range(n))))\nfor _ in range(q):\n\tangle = int(input().strip())\n\tprint(r[angle // 90 % 4])\n", "import sys\n\ndef hackonacci(d):\n\tif d == 1:\n\t\treturn 1\n\tif d == 2:\n\t\treturn 0\n\tif d == 3:\n\t\treturn 1\n\th = [0, 0, 1, 1, 1, 0, 1]\n\treturn h[(d - 4) % len(h)]\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\n\ndef rotated_diffs(s):\n\tdiffs = [0, 0, 0, 0]\n\tfor col in range(1, s // 2 + 1):\n\t\tfor row in range(1, s + 1):\n\t\t\tleft = hackonacci(pow(row * col, 2))\n\t\t\tright_reflect = hackonacci(pow(row * (s - col + 1), 2))\n\t\t\tdiffs[1] += int(left != right_reflect) * 2\n\tfor row in range(1, s + 1):\n\t\tfor col in range(1, s - row + 1):\n\t\t\ttop_left = hackonacci(pow(row * col, 2))\n\t\t\tbottom_right_reflect = hackonacci(pow((s - row + 1) * (s - col + 1), 2))\n\t\t\tdiffs[2] += int(top_left != bottom_right_reflect) * 2\n\tdiffs[3] = diffs[1]\n\treturn diffs\ndiffs_ = rotated_diffs(n)\nfor a0 in range(q):\n\tangle = int(input().strip()) % 360\n\tprint(diffs_[angle // 90])\n", "import sys\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nvlist = [1, 0, 1, 0, 0, 1, 1]\narr = [[vlist[(i * j) ** 2 % 7 - 1] for i in range(1, n + 1)] for j in range(1, n + 1)]\nresult = {}\nfor a0 in range(q):\n\tangle = int(input().strip())\n\t(tot, angle) = (0, angle % 360)\n\tif angle not in result:\n\t\tif angle == 90:\n\t\t\tres = list(zip(*arr[::-1]))\n\t\telif angle == 180:\n\t\t\tres = [row[::-1] for row in arr[::-1]]\n\t\telif angle == 270:\n\t\t\tres = list(zip(*arr[::-1]))\n\t\t\tres = [row[::-1] for row in res[::-1]]\n\t\telse:\n\t\t\tres = arr\n\t\tresult[angle] = sum([1 for i in range(n) for j in range(n) if res[i][j] != arr[i][j]])\n\ttot = result[angle]\n\tprint(tot)\n", "import sys\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nangle = [int(input().strip()) for a0 in range(q)]\nsq = [i * i for i in range(0, n + 1)]\nM = []\nfor i in range(1, n + 1):\n\tL = n * [False]\n\tfor j in range(1, n + 1):\n\t\tL[j - 1] = 1 if sq[i] * sq[j] % 7 in [0, 1, 3, 6] else 0\n\tM.append(L)\ncnt = [0, 0, 0, 0]\nN = n - 1\nfor i in range(0, n):\n\tfor j in range(0, n):\n\t\tcnt[3] += 0 if M[i][j] == M[j][N - i] else 1\n\t\tcnt[2] += 0 if M[i][j] == M[N - i][N - j] else 1\n\t\tcnt[1] += 0 if M[i][j] == M[N - j][i] else 1\nfor i in range(q):\n\tangle[i] = angle[i] % 360 // 90\n\tprint(cnt[angle[i]])\n", "import sys\n\ndef rotate(n, mat_arg):\n\tmat = [[item for item in row] for row in mat_arg]\n\tfor i in range(n // 2):\n\t\tfor j in range(i, n - i - 1):\n\t\t\ttmp = mat[i][j]\n\t\t\tmat[i][j] = mat[n - j - 1][i]\n\t\t\tmat[n - j - 1][i] = mat[n - i - 1][n - j - 1]\n\t\t\tmat[n - i - 1][n - j - 1] = mat[j][n - i - 1]\n\t\t\tmat[j][n - i - 1] = tmp\n\treturn mat\n\ndef guess(hack, i, j):\n\tidx = ((i + 1) * (j + 1)) ** 2 % 56\n\treturn 'Y' if hack[idx - 1] & 1 > 0 else 'X'\n\ndef get_diff(mat1, mat2):\n\tcnt = 0\n\tfor i in range(len(mat1)):\n\t\tfor j in range(len(mat1[0])):\n\t\t\tif mat1[i][j] != mat2[i][j]:\n\t\t\t\tcnt += 1\n\treturn cnt\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nhack = [0] * 1000\nhack[1] = 1\nhack[2] = 2\nhack[3] = 3\nfor i in range(4, 1000):\n\thack[i] = (hack[i - 1] + 2 * hack[i - 2] + 3 * hack[i - 3]) % 10\nhack = hack[1:57]\nmat = [[guess(hack, i, j) for j in range(n)] for i in range(n)]\nmats = []\nmats.append(mat)\ntemp = mat\nfor i in range(3):\n\ttemp = rotate(n, temp)\n\tmats.append(temp)\ndiffs = [0, get_diff(mats[0], mats[1]), get_diff(mats[0], mats[2]), get_diff(mats[0], mats[3])]\nfor a0 in range(q):\n\tangle = int(input().strip()) // 90 % 4\n\tprint(diffs[angle])\n", "import sys\n\ndef changesCount(matrix, degree):\n\tcount = 0\n\tif degree == 90:\n\t\tfor x in range(len(matrix)):\n\t\t\tfor i in range(len(matrix)):\n\t\t\t\tif matrix[x][i] != matrix[len(matrix) - 1 - i][x]:\n\t\t\t\t\tcount += 1\n\telif degree == 180:\n\t\tfor x in range(len(matrix)):\n\t\t\tfor i in range(len(matrix)):\n\t\t\t\tif matrix[x][i] != matrix[len(matrix) - 1 - x][len(matrix) - 1 - i]:\n\t\t\t\t\tcount += 1\n\telif degree == 270:\n\t\tfor x in range(len(matrix)):\n\t\t\tfor i in range(len(matrix)):\n\t\t\t\tif matrix[x][i] != matrix[i][len(matrix) - 1 - x]:\n\t\t\t\t\tcount += 1\n\treturn count\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nmatrix = [[] for x in range(n)]\ncounts = [[-1] for x in range(3)]\nfor i in range(0, n):\n\tfor x in range(0, n):\n\t\tnum = ((i + 1) * (x + 1)) ** 2\n\t\tnum = num % 7\n\t\tif num == 2 or num == 4 or num == 5:\n\t\t\tmatrix[i].append('X')\n\t\telse:\n\t\t\tmatrix[i].append('Y')\nfor a in range(q):\n\tangle = int(input().strip())\n\tdegree = angle % 360\n\tif degree == 90 and counts[0][0] == -1:\n\t\tcounts[0][0] = changesCount(matrix, degree)\n\t\tprint(counts[0][0])\n\telif degree == 90 and counts[0][0] != -1:\n\t\tprint(counts[0][0])\n\tif degree == 180 and counts[1][0] == -1:\n\t\tcounts[1][0] = changesCount(matrix, degree)\n\t\tprint(counts[1][0])\n\telif degree == 180 and counts[1][0] != -1:\n\t\tprint(counts[1][0])\n\tif degree == 270 and counts[2][0] == -1:\n\t\tcounts[2][0] = changesCount(matrix, degree)\n\t\tprint(counts[2][0])\n\telif degree == 270 and counts[2][0] != -1:\n\t\tprint(counts[2][0])\n\tif degree == 0:\n\t\tprint(0)\n", "import sys\nimport math\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nangle = []\nd = dict()\nd[0] = 0\nd[90] = None\nd[180] = None\nd[270] = None\nfor a0 in range(q):\n\tangle.append(int(input().strip()))\na = [0, 1, 6, 8, 15, 20, 36]\nMatrix = [[0 for x in range(n)] for y in range(n)]\nfor i in range(n):\n\tfor j in range(n):\n\t\tx = (j + 1) % 7 * ((i + 1) % 7)\n\t\tif x in a:\n\t\t\tMatrix[j][i] = 1\nfor c in angle:\n\tif d[c % 360] == None:\n\t\td[c % 360] = 0\n\t\tif c % 360 == 90:\n\t\t\tfor i in range(n):\n\t\t\t\tfor j in range(n):\n\t\t\t\t\tif Matrix[i][j] ^ Matrix[n - j - 1][i]:\n\t\t\t\t\t\td[90] = d[90] + 1\n\t\t\tprint(d[90])\n\t\tif c % 360 == 180:\n\t\t\tfor i in range(n):\n\t\t\t\tfor j in range(n):\n\t\t\t\t\tif Matrix[i][j] ^ Matrix[n - i - 1][n - j - 1]:\n\t\t\t\t\t\td[180] = d[180] + 1\n\t\t\tprint(d[180])\n\t\tif c % 360 == 270:\n\t\t\tfor i in range(n):\n\t\t\t\tfor j in range(n):\n\t\t\t\t\tif Matrix[i][j] ^ Matrix[j][n - i - 1]:\n\t\t\t\t\t\td[270] = d[270] + 1\n\t\t\tprint(d[270])\n\telse:\n\t\tprint(d[c % 360])\n", "import sys\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\n\ndef f(i, j):\n\treturn [1, 1, 0, 1, 0, 0, 1][(i * j) ** 2 % 7]\n(ans90, ans180) = (0, 0)\nfor i in range(1, n // 2 + 1):\n\tfor j in range(1, (n + 1) // 2 + 1):\n\t\ta = [f(i, j), f(n + 1 - j, i), f(n + 1 - i, n + 1 - j), f(j, n + 1 - i)]\n\t\tans90 += abs(a[0] - a[1]) + abs(a[1] - a[2]) + abs(a[2] - a[3]) + abs(a[3] - a[0])\n\t\tans180 += abs(a[0] - a[2]) * 2 + abs(a[1] - a[3]) * 2\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tprint([0, ans90, ans180, ans90][angle % 360 // 90])\n", "def hl(n):\n\treturn 'YYXYXXY'[n % 7]\n\ndef f(n):\n\tquarter = 0\n\thalf = 0\n\tfor i in range(1, 1 + n):\n\t\tfor j in range(1, 1 + n):\n\t\t\t(i1, j1) = (j, n + 1 - i)\n\t\t\t(i2, j2) = (n + 1 - i, n + 1 - j)\n\t\t\tthis_letter = hl((i * j) ** 2)\n\t\t\tquarter_letter = hl((i1 * j1) ** 2)\n\t\t\thalf_letter = hl((i2 * j2) ** 2)\n\t\t\tquarter += this_letter != quarter_letter\n\t\t\thalf += this_letter != half_letter\n\treturn (quarter, half)\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\n(qu, ha) = f(n)\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tif angle % 360 == 0:\n\t\tprint(0)\n\telif angle % 180 == 0:\n\t\tprint(ha)\n\telse:\n\t\tprint(qu)\n", "import sys\nhack = [False, False, True, False, True, True, False]\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nX = [['X' if hack[((i + 1) * (j + 1)) ** 2 % 7] else 'Y' for j in range(n)] for i in range(n)]\n\ndef not_equals_new_pos(i, j, m):\n\tif m % 4 == 0:\n\t\treturn False\n\tif m % 4 == 1:\n\t\treturn X[i][j] != X[i][n - j - 1]\n\tif m % 4 == 2:\n\t\treturn X[i][j] != X[n - i - 1][n - j - 1]\n\tif m % 4 == 3:\n\t\treturn X[i][j] != X[n - i - 1][j]\nD = {m: sum((not_equals_new_pos(i, j, m) for i in range(n) for j in range(n))) for m in range(4)}\nfor a0 in range(q):\n\tprint(D[int(input().strip()) // 90 % 4])\n", "import sys\npattern = [1, 0, 1, 0, 0, 1, 1]\nmatrix = []\nn = 0\n\ndef prep_matrix():\n\tfor i in range(n):\n\t\tmatrix.append([False] * n)\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tk = (i + 1) * (j + 1)\n\t\t\tk *= k\n\t\t\tmatrix[i][j] = pattern[(k - 1) % len(pattern)]\n\ndef count90():\n\tresult = 0\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tif matrix[i][j] != matrix[n - j - 1][i]:\n\t\t\t\tresult += 1\n\treturn result\n\ndef count180():\n\tresult = 0\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tif matrix[i][j] != matrix[n - i - 1][n - j - 1]:\n\t\t\t\tresult += 1\n\treturn result\n\ndef count270():\n\tresult = 0\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tif matrix[i][j] != matrix[j][n - i - 1]:\n\t\t\t\tresult += 1\n\treturn result\n(n, q) = map(int, input().strip().split())\nprep_matrix()\nresult = {}\nresult[0] = 0\nresult[90] = count90()\nresult[180] = count180()\nresult[270] = count270()\nfor a0 in range(q):\n\tangle = int(input().strip()) % 360\n\tprint(result[angle])\n", "import sys\nh_all = [None, 'X', 'Y', 'X', 'Y', 'Y', 'X', 'X', 'X']\n\ndef h(n):\n\tif n > 8:\n\t\tn = (n - 1) % 7\n\t\tn += 1\n\treturn h_all[n]\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nresults = [0, None, None, None]\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tangle = angle % 360\n\tz = int(angle / 90)\n\tif results[z] != None:\n\t\tprint(results[z])\n\telse:\n\t\ttotal = 0\n\t\tif z == 2:\n\t\t\tfor i in range(1, n + 1):\n\t\t\t\tfor j in range(1, i + 1):\n\t\t\t\t\tir = n - (i - 1)\n\t\t\t\t\tjr = n - (j - 1)\n\t\t\t\t\tif h((i * j) ** 2) != h((ir * jr) ** 2):\n\t\t\t\t\t\tif i == j:\n\t\t\t\t\t\t\ttotal += 1\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\ttotal += 2\n\t\t\tresults[z] = total\n\t\telse:\n\t\t\tjrange = n // 2\n\t\t\tg = None\n\t\t\tif n % 2:\n\t\t\t\tjrange += 1\n\t\t\t\tg = jrange\n\t\t\tfor i in range(1, n + 1):\n\t\t\t\tfor j in range(1, jrange + 1):\n\t\t\t\t\tir = n - j + 1\n\t\t\t\t\tjr = i\n\t\t\t\t\tif h((i * j) ** 2) != h((ir * jr) ** 2):\n\t\t\t\t\t\tif j == g:\n\t\t\t\t\t\t\ttotal += 1\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\ttotal += 2\n\t\t\tresults[1] = results[3] = total\n\t\tprint(total)\n", "import sys\n\ndef set_value(n):\n\tif n % 7 in (1, 3, 6, 0):\n\t\treturn 'Y'\n\telse:\n\t\treturn 'X'\n\ndef rotate_90(matrice):\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tr_matrice[i][j] = matrice[n - 1 - j][i]\n\treturn r_matrice\n\ndef rotate_180(matrice):\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tr_matrice[i][j] = matrice[n - 1 - i][n - 1 - j]\n\treturn r_matrice\n\ndef rotate_270(matrice):\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tr_matrice[i][j] = matrice[j][n - 1 - i]\n\treturn r_matrice\n\ndef compare(m1, m2):\n\tdiff = 0\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tif m1[i][j] != m2[i][j]:\n\t\t\t\tdiff += 1\n\treturn diff\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nmatrice = [['Z' for _ in range(n)] for _ in range(n)]\nr_matrice = [['Z' for _ in range(n)] for _ in range(n)]\nfor i in range(n):\n\tfor j in range(n):\n\t\tmatrice[i][j] = set_value(((i + 1) * (j + 1)) ** 2)\ndiff_90 = compare(matrice, rotate_90(matrice))\ndiff_180 = compare(matrice, rotate_180(matrice))\ndiff_270 = compare(matrice, rotate_270(matrice))\nfor a0 in range(q):\n\tangle = int(input().strip()) % 360\n\tif angle == 90:\n\t\tprint(diff_90)\n\telif angle == 180:\n\t\tprint(diff_180)\n\telif angle == 270:\n\t\tprint(diff_270)\n\telse:\n\t\tprint('0')\n", "import sys\nhackonnaci_dict = dict({0: 'Y', 1: 'X', 2: 'Y', 3: 'X', 4: 'X', 5: 'Y', 6: 'Y'})\n\ndef hackonnaci(x):\n\treturn hackonnaci_dict[(x - 1) % 7]\n\ndef num_matrix_diffs(a, b):\n\tnum_diffs = 0\n\tfor i in range(len(a)):\n\t\tfor j in range(len(b)):\n\t\t\tif a[i][j] != b[i][j]:\n\t\t\t\tnum_diffs += 1\n\treturn num_diffs\n\ndef rotate(matrix):\n\ttemp_matrix = []\n\tfor row in matrix:\n\t\ttemp_matrix.append(row[::-1])\n\tresult = []\n\tfor tup in zip(*temp_matrix):\n\t\tresult.append(list(tup))\n\treturn result\n\ndef create_matrix(n):\n\tmat = []\n\tfor i in range(1, n + 1):\n\t\trow = []\n\t\tfor j in range(1, n + 1):\n\t\t\trow.append(hackonnaci((i * j) ** 2))\n\t\tmat.append(row)\n\treturn mat\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nmatrix0 = create_matrix(n)\nmatrix90 = rotate(matrix0)\nmatrix180 = rotate(matrix90)\nmatrix270 = rotate(matrix180)\ndiffs90 = num_matrix_diffs(matrix0, matrix90)\ndiffs180 = num_matrix_diffs(matrix0, matrix180)\ndiffs270 = num_matrix_diffs(matrix0, matrix270)\nfor a0 in range(q):\n\tangle = int(input().strip()) % 360\n\tif angle == 0:\n\t\tprint(0)\n\tif angle == 90:\n\t\tprint(diffs90)\n\tif angle == 180:\n\t\tprint(diffs180)\n\tif angle == 270:\n\t\tprint(diffs270)\n", "import sys\n\ndef hack_odd(n):\n\tif n == 1:\n\t\treturn 1\n\telse:\n\t\treturn [0, 1, 0, 0, 1, 1, 1][(n - 2) % 7]\n\ndef hack_matrix(n):\n\tresult = [[None for _ in range(n)] for _ in range(n)]\n\tfor r in range(n):\n\t\tfor c in range(n):\n\t\t\tif hack_odd(((r + 1) * (c + 1)) ** 2):\n\t\t\t\tresult[r][c] = 'y'\n\t\t\telse:\n\t\t\t\tresult[r][c] = 'x'\n\treturn result\n\ndef flip(mat, n):\n\treturn [[mat[r][n - 1 - c] for c in range(n)] for r in range(n)]\n\ndef rotate90(mat, n):\n\treturn flip([[mat[c][r] for c in range(n)] for r in range(n)], n)\nmemo_rots = {}\n\ndef rotate(mat, n, angle):\n\tangle = round(angle % 360 / 90)\n\tif angle in memo_rots:\n\t\treturn memo_rots[angle]\n\telse:\n\t\tfor i in range(1, angle + 1):\n\t\t\tmat = rotate90(mat, n)\n\t\t\tif i not in memo_rots:\n\t\t\t\tmemo_rots[i] = mat\n\t\treturn memo_rots[angle]\nmemo_diffs = {}\n\ndef num_diffs(mat, n, angle):\n\tif angle % 360 == 0:\n\t\treturn 0\n\telif angle % 360 in memo_diffs:\n\t\treturn memo_diffs[angle % 360]\n\telse:\n\t\tmat2 = rotate(mat, n, angle)\n\t\tdiffs = 0\n\t\tfor r in range(n):\n\t\t\tfor c in range(n):\n\t\t\t\tif mat[r][c] != mat2[r][c]:\n\t\t\t\t\tdiffs += 1\n\t\tmemo_diffs[angle % 360] = diffs\n\t\treturn diffs\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nmat = hack_matrix(n)\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tprint(num_diffs(mat, n, angle))\n", "(n, g) = map(int, input().split())\nhack = [1, 1, 0, 1, 0, 0, 1]\nA = [[] for i in range(n + 1)]\nfor i in range(1, n + 1):\n\tfor j in range(1, n + 1):\n\t\tif hack[i * i * j * j % 7] == 0:\n\t\t\tA[i].append('X')\n\t\telse:\n\t\t\tA[i].append('Y')\nB = []\nfor i in range(n + 1):\n\tif len(A[i]) != 0:\n\t\tB.append(A[i])\nrot90 = tuple(zip(*B[::-1]))\nrot180 = tuple(zip(*rot90[::-1]))\nrot270 = tuple(zip(*rot180[::-1]))\nans = [0, 0, 0, 0]\nfor i in range(n):\n\tfor j in range(n):\n\t\tif B[i][j] != rot90[i][j]:\n\t\t\tans[1] += 1\n\t\tif B[i][j] != rot180[i][j]:\n\t\t\tans[2] += 1\n\t\tif B[i][j] != rot270[i][j]:\n\t\t\tans[3] += 1\nfor k in range(g):\n\tq = int(input())\n\tif q % 360 == 0:\n\t\ta = ans[0]\n\telif q % 360 == 90:\n\t\ta = ans[1]\n\telif q % 360 == 180:\n\t\ta = ans[2]\n\telse:\n\t\ta = ans[3]\n\tprint(a)\n", "def solve(n, queries):\n\ta = [[((i + 1) * (j + 1)) ** 2 % 7 in [0, 1, 3, 6] for j in range(n)] for i in range(n)]\n\tb = a\n\tans = []\n\tfor i in range(4):\n\t\tdiff = 0\n\t\tfor i in range(n):\n\t\t\tfor j in range(n):\n\t\t\t\tif a[i][j] != b[i][j]:\n\t\t\t\t\tdiff += 1\n\t\tans.append(diff)\n\t\tb = rotate(b)\n\treturn [ans[q // 90 % 4] for q in queries]\n\ndef rotate(a):\n\treturn [[a[j][i] for j in range(len(a))] for i in range(len(a[0]) - 1, -1, -1)]\n\ndef test():\n\tassert solve(4, [90, 180, 270]) == [10, 6, 10]\n\tsolve(2000, [10 ** 5] * 10 ** 4)\n\ndef read_ints():\n\treturn list(map(int, input().split()))\n(n, q) = read_ints()\nqueries = [int(input()) for _ in range(q)]\nprint(*solve(n, queries), sep='\\n')\n", "from itertools import chain\nfrom operator import xor\nfrom collections import deque\nfrom math import sqrt\n\ndef is_square(n):\n\tsn = sqrt(n)\n\treturn sn - int(sn) < 1e-06\n\ndef rotate(X):\n\treturn [[X[n - j - 1][i] for j in range(n)] for i in range(n)]\n\ndef diff(x, y):\n\treturn sum(map(xor, chain(*x), chain(*y)))\n\ndef printm(X):\n\tprint(*X, sep='\\n', end='\\n\\n')\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nh = [1, 1, 0, 1, 0, 0, 1]\nm = [[h[(i * j) ** 2 % 7] for j in range(1, n + 1)] for i in range(1, n + 1)]\nm1 = rotate(m)\nm2 = rotate(m1)\nm3 = rotate(m2)\nstate = 0\nans = [[0 for j in range(4)] for i in range(4)]\nans[0][1] = ans[1][3] = diff(m, m1)\nans[0][2] = ans[2][2] = diff(m, m2)\nans[0][3] = ans[3][1] = diff(m, m3)\nans[1][1] = ans[2][3] = diff(m1, m2)\nans[1][2] = ans[3][2] = diff(m1, m3)\nans[2][1] = ans[3][3] = diff(m2, m3)\nfor a0 in range(q):\n\tangle = int(input().strip()) % 360 // 90\n\tprint(ans[state][angle])\n\tstate = (state + angle) % 4\n", "import sys\n\ndef solve1(n, dp):\n\tif n == 1 or n == 2 or n == 3:\n\t\treturn n\n\tif dp[n] != -1:\n\t\treturn dp[n]\n\tdp[n] = 1 * solve1(n - 1, dp) + 2 * solve1(n - 2, dp) + 3 * solve1(n - 3, dp)\n\treturn dp[n]\n\ndef solve(matrix, dp):\n\tfor i in range(7):\n\t\tfor j in range(7):\n\t\t\tanswer = dp[((i + 1) * (j + 1)) ** 2]\n\t\t\tif answer % 2 == 0:\n\t\t\t\tmatrix[i][j] = 'X'\n\t\t\telse:\n\t\t\t\tmatrix[i][j] = 'Y'\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nmatrix = [[0] * 7 for _ in range(7)]\ndp = [-1 for _ in range((7 * 7) ** 2 + 1)]\nfor i in range((7 * 7) ** 2 + 1)[1:]:\n\tif i == 1 or i == 2 or i == 3:\n\t\tdp[i] = i\n\telse:\n\t\tdp[i] = (1 * dp[i - 1] + 2 * dp[i - 2] + 3 * dp[i - 3]) % 10\nsolve(matrix, dp)\nlookup = matrix\nmat = [[-1] * n for _ in range(n)]\nfor i in range(n):\n\tfor j in range(n):\n\t\tif (i + 1) % 7 == 0 or (j + 1) % 7 == 0:\n\t\t\tmat[i][j] = 'Y'\n\t\telse:\n\t\t\tmat[i][j] = lookup[i % 7][j % 7]\nangle1 = [-1 for i in range(3)]\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tcount = 0\n\tif angle % 360 == 90:\n\t\tif angle1[0] != -1:\n\t\t\tcount = angle1[0]\n\t\telse:\n\t\t\tfor i in range(n):\n\t\t\t\tfor j in range(n):\n\t\t\t\t\tif mat[i][j] != mat[j][n - 1 - i]:\n\t\t\t\t\t\tcount += 1\n\t\t\tangle1[0] = count\n\tif angle % 360 == 180:\n\t\tif angle1[1] != -1:\n\t\t\tcount = angle1[1]\n\t\telse:\n\t\t\tfor i in range(n):\n\t\t\t\tfor j in range(n):\n\t\t\t\t\tif mat[i][j] != mat[n - 1 - i][n - 1 - j]:\n\t\t\t\t\t\tcount += 1\n\t\t\tangle1[1] = count\n\tif angle % 360 == 270:\n\t\tif angle1[2] != -1:\n\t\t\tcount = angle1[2]\n\t\telse:\n\t\t\tfor i in range(n):\n\t\t\t\tfor j in range(n):\n\t\t\t\t\tif mat[i][j] != mat[n - 1 - j][i]:\n\t\t\t\t\t\tcount += 1\n\t\t\tangle1[2] = count\n\tprint(count)\n", "from itertools import chain\nhack_pattern = (False, True, False, True, True, False, False)\n\ndef hackonacci_even(n):\n\treturn hack_pattern[(n - 1) % 7]\n\ndef matrix_rotate_90(mat):\n\treturn list(zip(*mat[::-1]))\n\ndef matrix_iter(mat):\n\treturn chain.from_iterable(mat)\n\ndef matrix_differences(mat1, mat2):\n\treturn sum((x != y for (x, y) in zip(matrix_iter(mat1), matrix_iter(mat2))))\n(n, q) = [int(x) for x in input().strip().split(' ')]\nmatrix = [[hackonacci_even(i * i * j * j) for j in range(1, n + 1)] for i in range(1, n + 1)]\nmat_differences = [0, 0, 0, 0]\nrotated_matrix = matrix\nfor i in range(1, 4):\n\trotated_matrix = matrix_rotate_90(rotated_matrix)\n\tmat_differences[i] = matrix_differences(matrix, rotated_matrix)\nfor _ in range(q):\n\tangle = int(input().strip())\n\trotations = angle % 360 // 90\n\tprint(mat_differences[rotations])\n", "def hackonacci(x):\n\tresult = (x - 2) % 7\n\tif result == 0 or result == 2 or result == 3:\n\t\treturn 0\n\telse:\n\t\treturn 1\n(n, q) = input().strip().split(' ')\n(n, q) = (int(n), int(q))\nboard = [None] * n\nboard90 = [None] * n\nboard180 = [None] * n\nboard270 = [None] * n\nfor i in range(n):\n\tboard[i] = [None] * n\n\tboard90[i] = [None] * n\n\tboard180[i] = [None] * n\n\tboard270[i] = [None] * n\nfor i in range(1, n + 1):\n\tfor k in range(1, n + 1):\n\t\tidx = i * k * i * k\n\t\tboard[i - 1][k - 1] = hackonacci(idx)\nfor i in range(n):\n\tfor k in range(n):\n\t\tidx = k\n\t\tidy = n - i - 1\n\t\tboard90[idx][idy] = board[i][k]\nfor i in range(n):\n\tfor k in range(n):\n\t\tboard180[n - i - 1][n - k - 1] = board[i][k]\nfor i in range(n):\n\tfor k in range(n):\n\t\tboard270[n - i - 1][n - k - 1] = board90[i][k]\ndiff90 = 0\ndiff180 = 0\ndiff270 = 0\nfor i in range(n):\n\tfor k in range(n):\n\t\tif board90[i][k] != board[i][k]:\n\t\t\tdiff90 += 1\n\t\tif board180[i][k] != board[i][k]:\n\t\t\tdiff180 += 1\n\t\tif board270[i][k] != board[i][k]:\n\t\t\tdiff270 += 1\nfor i in range(q):\n\tangle = int(input().strip())\n\tangle = angle % 360 / 90\n\tif angle == 1:\n\t\tprint(diff90)\n\telif angle == 2:\n\t\tprint(diff180)\n\telif angle == 3:\n\t\tprint(diff270)\n\telse:\n\t\tprint(0)\n", "import sys\n\ndef h(n):\n\tif n in [1, 2, 3]:\n\t\treturn n\n\treturn 1 * h(n - 1) + 2 * h(n - 2) + 3 * h(n - 3)\n\ndef printm(m):\n\tfor a in m:\n\t\tprint(a)\n\tprint('------------------')\n\ndef rotate90(m):\n\t(B, lenm) = ([], len(m))\n\tfor r in range(0, lenm):\n\t\tbrow = ''\n\t\tfor c in range(lenm - 1, -1, -1):\n\t\t\tbrow += m[c][r]\n\t\tB.append(brow)\n\treturn B\n\ndef rotate180(m):\n\t(B, lenm) = ([], len(m))\n\tfor r in range(0, lenm):\n\t\tbrow = ''\n\t\tfor c in range(lenm - 1, -1, -1):\n\t\t\tbrow += m[lenm - r - 1][c]\n\t\tB.append(brow)\n\treturn B\n\ndef rotate270(m):\n\t(B, lenm) = ([], len(m))\n\tfor r in range(lenm - 1, -1, -1):\n\t\tbrow = ''\n\t\tfor c in range(0, lenm):\n\t\t\tbrow += m[c][r]\n\t\tB.append(brow)\n\treturn B\n\ndef m(n):\n\tB = ['1000011', '0011001', '0100101', '0100101', '0011001', '1000011', '1111111']\n\tA = []\n\tfor r in range(1, n + 1):\n\t\tr7 = r % 7 - 1\n\t\tif r7 == -1:\n\t\t\tr7 = 6\n\t\ts = ''\n\t\tfor c in range(1, n + 1):\n\t\t\tc7 = c % 7 - 1\n\t\t\tif c7 == -1:\n\t\t\t\tc7 = 6\n\t\t\ts += B[r7][c7]\n\t\tA.append(s)\n\treturn A\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nA = m(n)\nB = rotate90(A)\nC = rotate180(A)\nD = rotate270(A)\n(tot90, tot180, tot270) = (0, 0, 0)\nfor r in range(0, n):\n\tfor c in range(0, n):\n\t\tif A[r][c] != B[r][c]:\n\t\t\ttot90 += 1\n\t\tif A[r][c] != C[r][c]:\n\t\t\ttot180 += 1\n\t\tif A[r][c] != D[r][c]:\n\t\t\ttot270 += 1\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tangle %= 360\n\tif angle == 0:\n\t\tprint(0)\n\telif angle == 90:\n\t\tprint(tot90)\n\telif angle == 180:\n\t\tprint(tot180)\n\telse:\n\t\tprint(tot270)\n", "def hacko(n):\n\tp = n % 7\n\tif p < 2 or p == 6:\n\t\treturn 1\n\telse:\n\t\treturn 0\n\ndef r90(x, y, size):\n\tif hacko(x * y) == hacko(y * (size - x + 1)):\n\t\treturn 0\n\telse:\n\t\treturn 1\n\ndef r180(x, y, size):\n\tif hacko(x * y) == hacko((size - x + 1) * (size - y + 1)):\n\t\treturn 0\n\telse:\n\t\treturn 1\n(n, q) = [int(i) for i in input().split()]\n(r1, r2) = (0, 0)\nout = []\nfor i in range(1, n + 1):\n\tfor j in range(1, n + 1):\n\t\tr1 += r90(i, j, n)\n\t\tr2 += r180(i, j, n)\nfor _ in range(q):\n\tangle = int(input()) % 360\n\tif angle == 0:\n\t\tout.append('0')\n\telif angle == 180:\n\t\tout.append(str(r2))\n\telse:\n\t\tout.append(str(r1))\nprint('\\n'.join(out))\n", "import sys\nimport time\n\ndef mtx_el(i, j):\n\tvalue_store = [1, 0, 1, 0, 0, 1, 1]\n\treturn value_store[(i * i * j * j - 1) % 7]\n\ndef get_angle(a):\n\treturn a % 360\n\ndef rotate_90(n):\n\ts = 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)])\n\treturn s\n\ndef rotate_180(n):\n\ts = 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)])\n\treturn s\n\ndef rotate_270(n):\n\ts = 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)])\n\treturn s\n\ndef rotate(a, n):\n\tangle = get_angle(a)\n\tif angle == 0:\n\t\treturn 0\n\tif angle == 90:\n\t\treturn rotate_90(n)\n\tif angle == 180:\n\t\treturn rotate_180(n)\n\tif angle == 270:\n\t\treturn rotate_270(n)\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nrdict = {0: 0}\nrdict[90] = rotate(90, n)\nrdict[180] = rotate(180, n)\nrdict[270] = rdict[90]\nfor i in range(q):\n\tangle = get_angle(int(input().strip()))\n\tprint(rdict[angle])\n", "import sys\n\ndef hacko_parity(i):\n\tparity = {0: 1, 1: 0, 2: 1, 3: 0, 4: 0, 5: 1, 6: 1}\n\ti = (i - 1) % 7\n\treturn parity[i]\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nmatrix = [[0 for c in range(n)] for r in range(n)]\nfor c in range(n):\n\tfor r in range(n):\n\t\tif hacko_parity(((c + 1) * (r + 1)) ** 2):\n\t\t\tmatrix[r][c] = 'Y'\n\t\telse:\n\t\t\tmatrix[r][c] = 'X'\n(rotate_90, rotate_180) = (0, 0)\nfor c in range(n):\n\tfor r in range(n):\n\t\tif matrix[r][c] != matrix[c][n - 1 - r]:\n\t\t\trotate_90 += 1\n\t\tif matrix[r][c] != matrix[n - 1 - r][n - 1 - c]:\n\t\t\trotate_180 += 1\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tangle %= 360\n\tif angle == 0:\n\t\tprint(0)\n\telif angle == 180:\n\t\tprint(rotate_180)\n\telse:\n\t\tprint(rotate_90)\n", "import sys\n\ndef hackonacci(n):\n\thn = {1: 1, 2: 2, 3: 3}\n\n\tdef hcknc(n):\n\t\tif n not in hn:\n\t\t\thn[n] = hcknc(n - 1) + 2 * hcknc(n - 2) + 3 * hcknc(n - 3)\n\t\treturn hn[n]\n\treturn hcknc(n)\n(n, q) = [int(s) for s in input().strip().split(' ')]\nnacci0 = [2, 4, 5]\nmat = [[1] * n for i in range(n)]\nfor i in range(1, n + 1):\n\tfor j in range(i, n + 1):\n\t\tif i * i * j * j % 7 in nacci0:\n\t\t\tmat[i - 1][j - 1] = 0\n\t\t\tmat[j - 1][i - 1] = 0\nres = [0] * 4\nfor i in range(n):\n\tfor j in range(n):\n\t\tres[1] += abs(mat[i][j] - mat[j][n - 1 - i])\n\t\tres[2] += abs(mat[i][j] - mat[n - 1 - i][n - 1 - j])\n\t\tres[3] += abs(mat[i][j] - mat[n - 1 - j][i])\nfor i in range(q):\n\ta = int(input().strip())\n\tprint(res[a // 90 % 4])\n", "def x(i, j):\n\ts = (i + 1) * (j + 1) % 7\n\ts = (s + 7) % 7\n\treturn 1 if 2 <= s <= 5 else 0\n\ndef qry(n, a):\n\tif a == 0:\n\t\treturn 0\n\tif n % 7 == 6:\n\t\treturn 0\n\tn -= 1\n\tm = []\n\tfor i in range(7):\n\t\tif a == 180:\n\t\t\tm.append([x(i, j) ^ x(n - i, n - j) for j in range(7)])\n\t\telif a == 90:\n\t\t\tm.append([x(i, j) ^ x(n - j, i) for j in range(7)])\n\t\telif a == 270:\n\t\t\tm.append([x(i, j) ^ x(j, n - i) for j in range(7)])\n\t(u, v) = (n // 7, n % 7)\n\t(n, v) = (n + 1, v + 1)\n\treturn 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(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nfor a0 in range(q):\n\tangle = int(input().strip()) % 360\n\tprint(qry(n, angle))\n", "(n, q) = map(int, input().split())\nangles = [int(input()) for i in range(q)]\na = [1, 1, 0, 1, 0, 0, 1]\nquarter = half = 0\nfor i in range(1, n + 1):\n\tni = n - i + 1\n\tii = i * i\n\tnii = ni * ni\n\tfor j in range(1, n + 1):\n\t\tif a[ii * j * j % 7] != a[nii * j * j % 7]:\n\t\t\tquarter += 1\n\t\tif a[ii * j * j % 7] != a[nii * (n - j + 1) ** 2 % 7]:\n\t\t\thalf += 1\nanswer = [0, quarter, half, quarter]\nprint(*[answer[i // 90 % 4] for i in angles], sep='\\n')\n", "import sys\nimport math\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\ndegrees = []\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tdegrees.append(angle)\n\ndef hack(n):\n\tif n < 4:\n\t\treturn n % 2 == 0\n\tn = (n - 4) % 7\n\treturn n < 2 or n == 5\n\ndef create_matrix(n):\n\tmatrix = [[0 for x in range(n)] for y in range(n)]\n\tfor row in range(0, n):\n\t\tfor column in range(0, n):\n\t\t\tif hack(((row + 1) * (column + 1)) ** 2):\n\t\t\t\tmatrix[row][column] = '#'\n\t\t\telse:\n\t\t\t\tmatrix[row][column] = '.'\n\treturn matrix\n\ndef print_matrix(m):\n\tfor row in m:\n\t\tprint(*row)\n\tprint('')\nrot_mem = {}\n\ndef rotate_clockwise(matrix, degree):\n\tif degree in rot_mem:\n\t\treturn rot_mem[degree]\n\tfor i in range(1, int(degree / 90) + 1):\n\t\tmatrix = list(zip(*matrix[::-1]))\n\trot_mem[degree] = matrix\n\treturn matrix\n\ndef naive_count(matrix, degree):\n\tcount = 0\n\tmatrix_rotate = rotate_clockwise(matrix, degree)\n\tfor i in range(0, n):\n\t\tfor j in range(0, n):\n\t\t\tif matrix[i][j] != matrix_rotate[i][j]:\n\t\t\t\tcount = count + 1\n\treturn count\n\ndef opt_count(matrix, degree):\n\tcount = 0\n\thalf = math.floor(len(matrix) / 2)\n\tmatrix_rotate = rotate_clockwise(matrix, degree)\n\trange_n = range(0, n)\n\tfor i in range_n:\n\t\tfor j in range(0, half):\n\t\t\tif matrix[i][j] != matrix_rotate[i][j]:\n\t\t\t\tcount = count + 1\n\tcount = count * 2\n\tif len(matrix) % 2 != 0:\n\t\tfor i in range_n:\n\t\t\tif matrix[i][half] != matrix_rotate[i][half]:\n\t\t\t\tcount = count + 1\n\treturn count\n\ndef round_degree(degree):\n\tdegree = degree % 360\n\tif degree == 270:\n\t\tdegree = 90\n\treturn degree\ncount_mem = {}\n\ndef run(range_n):\n\tfor n in range_n:\n\t\tmatrix = create_matrix(n)\n\t\tfor degree in degrees:\n\t\t\tcount = 0\n\t\t\tdegree = round_degree(degree)\n\t\t\tif degree in count_mem:\n\t\t\t\tcount = count_mem[degree]\n\t\t\telse:\n\t\t\t\tcount = opt_count(matrix, degree) if degree != 0 else 0\n\t\t\t\tcount_mem[degree] = count\n\t\t\tprint(count)\nrun([n])\n", "import sys\ndic = {1: 'Y', 3: 'Y', 6: 'Y', 0: 'Y', 2: 'X', 4: 'X', 5: 'X'}\nY_dic = {}\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nfor i in range(1, n + 1):\n\tfor j in range(i, n + 1):\n\t\tif dic[i ** 2 * j ** 2 % 7] == 'Y':\n\t\t\tY_dic[i, j] = 1\n\t\t\tif i != j:\n\t\t\t\tY_dic[j, i] = 1\ntransform = {}\n\ndef rotate_90(coordinate):\n\treturn (coordinate[1], n + 1 - coordinate[0])\nrotate_1 = 0\nrotate_2 = 0\nrotate_3 = 0\nfor y in Y_dic:\n\ttemp = rotate_90(y)\n\tif temp not in Y_dic:\n\t\trotate_1 += 2\n\ttemp = rotate_90(temp)\n\tif temp not in Y_dic:\n\t\trotate_2 += 2\n\ttemp = rotate_90(temp)\n\tif temp not in Y_dic:\n\t\trotate_3 += 2\ntransform[1] = rotate_1\ntransform[2] = rotate_2\ntransform[3] = rotate_3\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tvalue = angle / 90 % 4\n\tif value == 0:\n\t\tprint(0)\n\telse:\n\t\tprint(transform[value])\n", "import sys\n\ndef sum_M(x, y, mat):\n\ts = 0\n\tfor i in range(1, x + 1):\n\t\tfor j in range(1, y + 1):\n\t\t\ts += mat[i % 7][j % 7]\n\treturn s\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nn1 = n % 7\nn2 = n // 7\nM = [[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]]\nmod7 = [1, 1, 0, 1, 0, 0, 1]\nP90 = [[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]]\nP180 = [[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]]\nP270 = [[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]]\nfor i in range(7):\n\tfor j in range(7):\n\t\tif M[i][j] != M[j][(n1 + 1 - i) % 7]:\n\t\t\tP90[i][j] = 1\n\t\tif M[i][j] != M[(n1 + 1 - i) % 7][(n1 + 1 - j) % 7]:\n\t\t\tP180[i][j] = 1\n\t\tif M[i][j] != M[(n1 + 1 - j) % 7][i]:\n\t\t\tP270[i][j] = 1\ncount90 = sum_M(7, 7, P90)\ncount180 = sum_M(7, 7, P180)\ncount270 = sum_M(7, 7, P270)\nfor a0 in range(q):\n\tangle = int(input().strip()) % 360\n\tif angle == 0 or n1 == 6:\n\t\tprint(0)\n\t\tcontinue\n\telif angle == 90:\n\t\tcount = n2 ** 2 * count90\n\t\tcount += n2 * (sum_M(n1, 7, P90) + sum_M(7, n1, P90))\n\t\tcount += sum_M(n1, n1, P90)\n\t\tprint(count)\n\telif angle == 180:\n\t\tcount = n2 ** 2 * count180\n\t\tcount += n2 * (sum_M(n1, 7, P180) + sum_M(7, n1, P180))\n\t\tcount += sum_M(n1, n1, P180)\n\t\tprint(count)\n\telif angle == 270:\n\t\tcount = n2 ** 2 * count90\n\t\tcount += n2 * (sum_M(n1, 7, P270) + sum_M(7, n1, P270))\n\t\tcount += sum_M(n1, n1, P270)\n\t\tprint(count)\n", "import sys\n\ndef h_bit(n):\n\tif n == 1:\n\t\treturn 1\n\treturn seq[(n - 2) % 7]\nseq = [0, 1, 0, 0, 1, 1, 1]\n\ndef cell(i, j):\n\treturn h_bit((i * j) ** 2)\n\ndef matrix(n):\n\treturn [[cell(i + 1, j + 1) for j in range(n)] for i in range(n)]\n\ndef get_rot(row, col, n, rot):\n\tnew_row = row\n\tif rot == 270 or rot == 180:\n\t\tnew_row = n - row - 1\n\tnew_col = col\n\tif rot == 90 or rot == 180:\n\t\tnew_col = n - col - 1\n\treturn (new_row, new_col)\ncompare_memo = {}\n\ndef compare(m, n, rot):\n\tif rot >= 360:\n\t\treturn compare(m, n, rot % 360)\n\tif rot == 0:\n\t\treturn 0\n\tif rot == 270:\n\t\treturn compare(m, n, 90)\n\tif rot in compare_memo:\n\t\treturn compare_memo[rot]\n\tdiff = 0\n\tfor row in range(n):\n\t\tfor col in range(n):\n\t\t\t(rot_row, rot_col) = get_rot(row, col, n, rot)\n\t\t\tif m[rot_row][rot_col] != m[row][col]:\n\t\t\t\tdiff += 1\n\tcompare_memo[rot] = diff\n\treturn diff\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nm = matrix(n)\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tprint(compare(m, n, angle))\n", "import sys\nchecker = [False, False, True, False, True, True, False, False]\n\ndef HH(gen):\n\tpos = gen % 7\n\treturn checker[pos]\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nmatrix = [[HH((x + 1) * (y + 1) * ((x + 1) * (y + 1))) for x in range(n)] for y in range(n)]\n\ndef tp270(i, j):\n\treturn matrix[n - i - 1][j]\n\ndef tp180(i, j):\n\treturn matrix[n - i - 1][n - j - 1]\n\ndef tp90(i, j):\n\treturn matrix[i][n - j - 1]\n\ndef tp0(i, j):\n\treturn matrix[i][j]\nans = [-1, -1, -1, -1]\n\ndef calcAns(pos):\n\tif ans[pos] != -1:\n\t\treturn ans[pos]\n\telse:\n\t\tans[pos] = 0\n\t\tif pos == 1:\n\t\t\tfunc = tp90\n\t\telif pos == 2:\n\t\t\tfunc = tp180\n\t\telif pos == 3:\n\t\t\tfunc = tp270\n\t\telse:\n\t\t\tfunc = tp0\n\t\tfor a in range(n):\n\t\t\tfor b in range(n):\n\t\t\t\tif matrix[a][b] != func(a, b):\n\t\t\t\t\tans[pos] += 1\n\t\treturn ans[pos]\nfor a0 in range(q):\n\tangle = int(input().strip())\n\ttranslate = angle % 360 // 90\n\tprint(calcAns(translate))\n", "import sys\n\nclass Matrix:\n\n\tdef __init__(self, n):\n\t\tself.n = n\n\t\tself.grid = []\n\t\tfor i in range(1, n + 1):\n\t\t\trow = []\n\t\t\tfor j in range(1, n + 1):\n\t\t\t\trow.append('Y' if self.parity((i * j) ** 2 - 1) else 'X')\n\t\t\tself.grid.append(row)\n\t\tself.differences = [0, 0, 0, 0]\n\t\tself.right = 0\n\t\tself.full = 0\n\t\tself.left = 0\n\n\tdef parity(self, n):\n\t\tv = n % 7\n\t\tif v == 0 or v == 2 or v == 5 or (v == 6):\n\t\t\treturn True\n\t\telse:\n\t\t\treturn False\n\n\tdef find_differences(self, n):\n\t\tright = 0\n\t\tfull = 0\n\t\tleft = 0\n\t\tfor i in range(n):\n\t\t\tfor j in range(n):\n\t\t\t\tif self.grid[i][j] != self.grid[n - (j + 1)][i]:\n\t\t\t\t\tright += 1\n\t\t\t\tif self.grid[i][j] != self.grid[n - (i + 1)][n - (j + 1)]:\n\t\t\t\t\tfull += 1\n\t\t\t\tif self.grid[i][j] != self.grid[n - (j + 1)][i]:\n\t\t\t\t\tleft += 1\n\t\tself.differences[1] = right\n\t\tself.differences[2] = full\n\t\tself.differences[3] = left\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nmatrix = Matrix(n)\nmatrix.find_differences(n)\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tprint(matrix.differences[angle % 360 // 90])\n", "(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\narr = [0, 0, 1, 0, 1, 1, 0]\ngrid = []\nfor i in range(n):\n\trow = []\n\tfor j in range(n):\n\t\tproduct = (i + 1) * (j + 1)\n\t\ttemp = product ** 2\n\t\trow.append(arr[temp % 7])\n\tgrid.append(row)\ndifferences = [0]\nfor a in [90, 180, 270]:\n\tnumDifferences = 0\n\tif a == 90:\n\t\tfor i in range(n):\n\t\t\tfor j in range(n):\n\t\t\t\tif grid[i][j] != grid[n - 1 - j][i]:\n\t\t\t\t\tnumDifferences += 1\n\t\tdifferences.append(numDifferences)\n\telif a == 180:\n\t\tfor i in range(n // 2):\n\t\t\tfor j in range(n):\n\t\t\t\tif grid[i][j] != grid[n - 1 - i][n - 1 - j]:\n\t\t\t\t\tnumDifferences += 2\n\t\tif n % 2 == 1:\n\t\t\tfor i in range(n // 2):\n\t\t\t\tif grid[n // 2][i] != grid[n // 2][n - 1 - i]:\n\t\t\t\t\tnumDifferences += 2\n\t\tdifferences.append(numDifferences)\n\telif a == 270:\n\t\tfor i in range(n):\n\t\t\tfor j in range(n):\n\t\t\t\tif grid[i][j] != grid[j][n - 1 - i]:\n\t\t\t\t\tnumDifferences += 1\n\t\tdifferences.append(numDifferences)\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tangle = angle % 360\n\tprint(differences[angle // 90])\n", "import sys\n\ndef isEven(n):\n\tr = n % 7\n\treturn 1 if r == 0 or r == 1 or r == 3 or (r == 6) else 0\n\ndef addToAns(a, b, c, d, ans):\n\ts = a + b + c + d\n\tif s == 0 or s == 4:\n\t\treturn\n\telif s == 1 or s == 3:\n\t\tans[1] += 2\n\t\tans[2] += 2\n\t\tans[3] += 2\n\telif a == c:\n\t\tans[1] += 4\n\t\tans[3] += 4\n\telse:\n\t\tans[2] += 4\n\t\tans[1] += 2\n\t\tans[3] += 2\n\ndef getAns(n):\n\tans = [0, 0, 0, 0]\n\tmid = n // 2 + 1\n\tfor x in range(1, mid + n % 2):\n\t\tfor y in range(1, mid):\n\t\t\t(x1, x2, x3, x4) = (x, n + 1 - y, n + 1 - x, y)\n\t\t\t(y1, y2, y3, y4) = (y, x, n + 1 - y, n + 1 - x)\n\t\t\t(a, b, c, d) = ((x1 * y1) ** 2, (x2 * y2) ** 2, (x3 * y3) ** 2, (x4 * y4) ** 2)\n\t\t\t(a, b, c, d) = (isEven(a), isEven(b), isEven(c), isEven(d))\n\t\t\taddToAns(a, b, c, d, ans)\n\treturn ans\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nans = getAns(n)\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tprint(ans[angle // 90 % 4])\n", "import sys\n\ndef hack(n):\n\tif n == 0 or n == 1 or n == 3:\n\t\treturn 1\n\tif n == 2:\n\t\treturn 0\n\telse:\n\t\treturn hack(n - 1) ^ hack(n - 3)\nmemo_hack = [hack(n) for n in range(7)]\nop1 = [[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]]\nop2 = [[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]]\n\ndef ops1(n):\n\tcoefs = op1[n % 7]\n\treturn round(coefs[0] * n ** 2 + coefs[1] * n + coefs[2])\n\ndef ops2(n):\n\tcoefs = op2[n % 7]\n\treturn round(coefs[0] * n ** 2 + coefs[1] * n + coefs[2])\n\ndef solution(n, rot):\n\tif rot == 0:\n\t\treturn 0\n\tif rot == 1 or rot == 3:\n\t\treturn ops1(n)\n\telse:\n\t\treturn ops2(n)\n\ndef hackarr(c):\n\treturn memo_hack[(c[0] * c[1]) ** 2 % 7]\n\ndef rot1(c, n):\n\treturn (c[1], n - c[0] + 1)\n\ndef rot2(c, n):\n\treturn (n - c[0] + 1, n - c[1] + 1)\n\ndef diag(n):\n\tfor i in range(1, n + 1):\n\t\tfor j in range(1, n + 1):\n\t\t\tyield (i, j)\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nfor a0 in range(q):\n\tangle = int(input().strip())\n\trot = angle // 90 % 4\n\tprint(solution(n, rot))\n", "(n, q) = map(int, input().split())\nx = [1, 1, 0, 1, 0, 0, 1]\na = []\nfor i in range(n):\n\tc = []\n\tfor j in range(n):\n\t\tz = (i + 1) * (j + 1) * (i + 1) * (j + 1)\n\t\tp = z % 7\n\t\tc.append(x[p])\n\ta.append(c)\nans = [0]\no = a\nfor a0 in range(4):\n\tcount = 0\n\tb = []\n\tfor i in range(n):\n\t\tm = []\n\t\tfor j in range(n):\n\t\t\tm.append(a[n - j - 1][i])\n\t\tb.append(m)\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tif o[i][j] != b[i][j]:\n\t\t\t\tcount = count + 1\n\tans.append(count)\n\ta = b\nfor k in range(q):\n\tang = int(input())\n\tang = ang // 90\n\tang = ang % 4\n\tprint(ans[ang])\n", "import sys\n\ndef corrected_angle(angle):\n\treturn angle % 360 // 90\n\ndef hackonacci(n):\n\tpattern = [False, False, True, False, True, True, False]\n\treturn pattern[n % 7]\n\ndef rotations(n):\n\tarr = gen(n)\n\tcount90_270 = 0\n\tcount180 = 0\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tcount90_270 += not arr[i][j] is arr[n - j - 1][i]\n\t\t\tcount180 += not arr[i][j] is arr[n - i - 1][n - j - 1]\n\treturn (count90_270, count180)\n\ndef gen(n):\n\tpattern = []\n\tfor i in range(1, n + 1):\n\t\tpattern.append([])\n\t\tfor j in range(1, n + 1):\n\t\t\tif hackonacci((i * j) ** 2):\n\t\t\t\tres = 'X'\n\t\t\telse:\n\t\t\t\tres = 'Y'\n\t\t\tpattern[i - 1].append(res)\n\treturn pattern\n\ndef display(pattern):\n\tn = len(pattern)\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tprint(pattern[i][j], end=' ')\n\t\tprint()\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nrot = rotations(n)\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tca = corrected_angle(angle)\n\tif ca == 0:\n\t\tprint(0)\n\telif ca == 1 or ca == 3:\n\t\tprint(rot[0])\n\telif ca == 2:\n\t\tprint(rot[1])\n", "(n, q) = [int(i) for i in input().split()]\nV = [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]\nd = {0: 0}\nfor _ in range(q):\n\tcount = 0\n\tangle = int(input()) % 360\n\tif angle in d:\n\t\tprint(d[angle])\n\telif angle == 90 or angle == 270:\n\t\tfor i in range(1, n + 1):\n\t\t\tk = 1\n\t\t\tfor j in range(n, 0, -1):\n\t\t\t\tif V[((i * j) ** 2 - 1) % 56] != V[((i * k) ** 2 - 1) % 56]:\n\t\t\t\t\tcount += 1\n\t\t\t\tk += 1\n\t\td[90] = count\n\t\td[270] = count\n\t\tprint(d[angle])\n\telif angle == 180:\n\t\tk = 1\n\t\tfor i in range(n, 0, -1):\n\t\t\tl = 1\n\t\t\tfor j in range(n, 0, -1):\n\t\t\t\tif V[((i * j) ** 2 - 1) % 56] != V[((k * l) ** 2 - 1) % 56]:\n\t\t\t\t\tcount += 1\n\t\t\t\tl += 1\n\t\t\tk += 1\n\t\td[angle] = count\n\t\tprint(d[angle])\n", "import sys\n\ndef diffc(a, b, n):\n\tcnt = 0\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tif a[i][j] != b[i][j]:\n\t\t\t\tcnt += 1\n\treturn cnt\n(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nhack = ['Y', 'Y', 'X', 'Y', 'X', 'X', 'Y', 'Y', 'Y']\nhackm = [[] for i in range(n)]\nfor i in range(n):\n\tfor j in range(n):\n\t\thackm[i].append(hack[pow((i + 1) * (j + 1), 2, 7)])\nhackm[0][0] = 'Y'\nninety = list(zip(*hackm[::-1]))\neighty = list(zip(*ninety[::-1]))\ntwo = list(zip(*eighty[::-1]))\nans = [0]\nans.append(diffc(hackm, ninety, n))\nans.append(diffc(hackm, eighty, n))\nans.append(diffc(hackm, two, n))\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tlocal = angle // 90\n\tlocal = local % 4\n\tprint(ans[local])\n", "from pprint import pprint\npattern = [1, 1, 0, 1, 0, 0, 1]\nm = len(pattern)\nmodkey = dict(zip(range(m), pattern))\n\ndef hack(x):\n\treturn modkey[x % m]\n(n, q) = map(int, input().split())\nar = [None]\nfor i in range(1, n + 1):\n\tar.append([hack((i * x) ** 2) for x in range(1, m + 1)])\nret = []\nrepeats = n // 7\nremainder = n % 7\nfor i in range(1, n + 1):\n\tt = []\n\tfullval = sum((0 if ar[i][j] == ar[n + 1 - i][j] else 1 for j in range(7)))\n\tpartval = sum((0 if ar[i][j] == ar[n + 1 - i][j] else 1 for j in range(remainder)))\n\tt.append(repeats * fullval + partval)\n\tfullval = sum((0 if ar[i][j] == ar[n + 1 - i][-((-remainder + 1 + j) % 7)] else 1 for j in range(7)))\n\tpartval = sum((0 if ar[i][j] == ar[n + 1 - i][-((-remainder + 1 + j) % 7)] else 1 for j in range(remainder)))\n\tt.append(repeats * fullval + partval)\n\tfullval = sum((0 if ar[i][j] == ar[i][-((-remainder + 1 + j) % 7)] else 1 for j in range(7)))\n\tpartval = sum((0 if ar[i][j] == ar[i][-((-remainder + 1 + j) % 7)] else 1 for j in range(remainder)))\n\tt.append(repeats * fullval + partval)\n\tret.append(t)\nscores = dict()\nscores[0] = 0\nscores[90] = sum((x[0] for x in ret))\nscores[180] = sum((x[1] for x in ret))\nscores[270] = sum((x[2] for x in ret))\nfor a0 in range(q):\n\tangle = int(input())\n\tangle = angle % 360\n\tprint(scores[angle])\n", "import sys, copy\nh = [['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(n, q) = input().strip().split(' ')\n(n, q) = [int(n), int(q)]\nm = []\nfor i in range(n):\n\tm.append([])\nfor i in range(n):\n\tfor j in range(n):\n\t\tm[i].append(h[i % 7][j % 7])\n(m1, m2, m3) = ([], [], [])\nfor i in range(n):\n\tm1.append([])\n\tm2.append([])\n\tm3.append([])\nresult = [0, 0, 0, 0]\nfor i in range(n):\n\tfor j in range(n):\n\t\tm1[i].append(m[n - j - 1][i])\ncount = 0\nfor i in range(n):\n\tfor j in range(n):\n\t\tif m[i][j] != m1[i][j]:\n\t\t\tcount += 1\nresult[1] = count\nfor i in range(n):\n\tfor j in range(n):\n\t\tm2[i].append(m[n - j - 1][n - i - 1])\ncount = 0\nfor i in range(n):\n\tfor j in range(n):\n\t\tif m[i][j] != m2[i][j]:\n\t\t\tcount += 1\nresult[2] = count\nfor i in range(n):\n\tfor j in range(n):\n\t\tm3[i].append(m[j][n - i - 1])\ncount = 0\nfor i in range(n):\n\tfor j in range(n):\n\t\tif m[i][j] != m3[i][j]:\n\t\t\tcount += 1\nresult[3] = count\nfor a0 in range(q):\n\tangle = int(input().strip())\n\tif angle >= 360:\n\t\twhile angle >= 360:\n\t\t\tangle -= 360\n\tnum = int(angle / 90)\n\tprint(result[num])\n"]

difficulty: MEDIUM

source: hacker rank

question:
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$:

![image](1.png)
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:

![image](2.png)

![image](3.png)

![image](4.png)
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.

image_tags: Math Math Math Math

data_split: test