Let's play a game!! Given a matrix mat[][] with n x m elements. Your task is to check that matrix is Super Similar or not. To perform this task you have to follow these Rules: Firstly all even index rows to be Rotated left and odd index rows to right, And Rotation is done X times(Index starting from zero). Secondly, After all the Rotations check if the initial and the final Matrix are same Return 1 else 0.
Example 1:
Input: n = 2, m = 2
mat = {{1, 2}, 
       {5, 6}}
x = 1
Output: 0
Explanation: Matrix after rotation:
mat = {{ 2, 1}
       { 6, 5}}
After one rotation mat is 
not same as the previous one.
 
Example 2:
Input: n = 2, m = 4
mat = {{1, 2, 1, 2}, 
       {2, 1, 2, 1}}
x = 2
Output: 1
Explanation: After two rotation mat is 
same as the previous one.
Your Task:
You do not need to read input or print anything. Your task is to complete the function isSuperSimilar() which takes n, m, x and the matrix as input parameter and returns 1 if the initial and the final Matrix are same else returns 0.
Expected Time Complexity: O(n*m)
Expected Auxiliary Space: O(n*m)
Constraints:
1 ≤ n, m ≤ 30
1 ≤ mat[i][j] ≤ 100 
1 ≤ x ≤ 20

Difficulty: MEDIUM_HARD
Tags: Matrices

Data structures
Skill types: Data structures
Expected Time Complexity: O(n*m)
Expected Auxiliary Space: O(n*m)

Starter code:
#User function Template for python3



class Solution:

    def isSuperSimilar(self, n, m, mat, x):

        # code here

Solutions:
class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		for i in range(n):
			for j in range(m):
				x %= m
				if i % 2 == 0:
					if mat[i][j] != mat[i][(j + x) % m]:
						return 0
				elif mat[i][j] != mat[i][(j + m - x) % m]:
					return 0
		return 1


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		temp = [[0 for i in range(m)] for j in range(n)]
		x = x % m
		for i in range(n):
			temp[i][0] = mat[i][x]
			k = 1
			j = (x + 1) % m
			while j != x:
				temp[i][k] = mat[i][j]
				k += 1
				j = (j + 1) % m
		for i in range(n):
			for j in range(m):
				if temp[i][j] != mat[i][j]:
					return 0
		return 1


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		arr1 = []
		for i in mat:
			l = []
			for j in i:
				l.append(j)
			arr1.append(l)
		for i in range(0, n, 2):
			for j in range(x):
				mat[i].insert(0, mat[i].pop())
		for i in range(1, n, 2):
			for j in range(x):
				mat[i].append(mat[i].pop(0))
		if arr1 == mat:
			return 1
		return 0


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		x = x % m
		grid = []
		for i in range(n):
			if i % 2:
				grid.append(mat[i][x:] + mat[i][:x])
			else:
				grid.append(mat[i][-x:] + mat[i][:-x])
		return int(grid == mat)


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		m2 = []
		x %= m
		for lis in range(n):
			if lis & 1 == 0:
				m2.append(mat[lis][-x:] + mat[lis][:-x])
			else:
				m2.append(mat[lis][x:] + mat[lis][:x])
		if m2 == mat:
			return 1
		return 0


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		if not mat:
			return
		x = x % m
		k = m - x
		for i in range(n):
			if i % 2 == 1:
				for j in range(m):
					if mat[i][j] != mat[i][(j + k) % m]:
						return 0
			else:
				for j in range(m):
					if mat[i][j] != mat[i][(j + x) % m]:
						return 0
		return 1


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		gen = [[*_] for _ in mat]
		x %= m
		for row in range(n):
			if row & 1 ^ 1:
				gen[row] = gen[row][x:] + gen[row][:x]
			else:
				gen[row] = gen[row][-x:] + gen[row][:-x]
		return int(gen == mat)


class Solution:

	def isSuperSimilar(self, n, m, mat, d):
		import copy
		temp = copy.deepcopy(mat)

		def rotate(arr, d, n):
			lar = max(arr) + 1
			start = d % n
			j = 0
			for i in range(start, start + n):
				arr[j] += arr[i % n] % lar * lar
				j += 1
			for i in range(n):
				arr[i] = arr[i] // lar
		for i in range(n):
			if i % 2 == 0:
				rotate(mat[i], d, m)
			else:
				rotate(mat[i], -d, m)
		return 1 if temp == mat else 0


class Solution:

	def swap(mat, inx, start, end):
		while start < end:
			(mat[inx][start], mat[inx][end]) = (mat[inx][end], mat[inx][start])
			start += 1
			end -= 1

	def isSuperSimilar(self, n, m, mat, d):
		chk = []
		for i in range(n):
			tmp = []
			for j in range(m):
				tmp.append(mat[i][j])
			chk.append(tmp)
		d %= m
		for i in range(n):
			if i % 2 == 0:
				Solution.swap(mat, i, 0, d - 1)
				Solution.swap(mat, i, d, m - 1)
				Solution.swap(mat, i, 0, m - 1)
			else:
				Solution.swap(mat, i, 0, m - 1)
				Solution.swap(mat, i, 0, d - 1)
				Solution.swap(mat, i, d, m - 1)
		if chk == mat:
			return 1
		return 0


class Solution:

	def right_rotate(self, arr, n, x):
		return arr[n - x:] + arr[:n - x]

	def isSuperSimilar(self, n, m, mat, x):
		x = x % m
		c = mat.copy()
		for i in range(n):
			if i % 2 == 0:
				mat[i] = self.right_rotate(mat[i], m, x)
			else:
				mat[i] = self.right_rotate(mat[i], m, m - x)
		for i in range(n):
			for j in range(m):
				if mat[i][j] != c[i][j]:
					return 0
		return 1


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		dupmat = [m for m in mat]
		if x >= m:
			x %= m
		for i in range(n):
			if (i + 1) % 2:
				temp = mat[i][m - x:]
				temp.extend(mat[i][:m - x])
				mat[i] = temp
			else:
				temp = mat[i][x:]
				temp.extend(mat[i][:x])
				mat[i] = temp
		compare = 1
		for i in range(n):
			if mat[i] != dupmat[i]:
				compare = 0
				break
		return compare


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		if x == 0:
			return 1
		for i in range(n):
			for j in range(m):
				fIndex = j
				sIndex = (j + x) % m
				first = mat[i][fIndex]
				second = mat[i][sIndex]
				if first != second:
					return 0
		return 1


class Solution:

	def isSuperSimilar(self, n, m, A, x):
		b = []
		x = x % m
		for i in range(n):
			if i % 2 == 0:
				b.append(A[i][x:] + A[i][:x])
			else:
				b.append(A[i][m - x:] + A[i][:m - x])
			if A[i] != b[i]:
				return 0
		return 1


class Solution:

	def isSuperSimilar(self, n, m, x, a):
		a = a % m
		o = 0
		y = [i.copy() for i in x]
		for i in range(n):
			if o == 0:
				x[i] = x[i][-a:] + x[i][:a]
			else:
				x[i] = x[i][a:] + x[i][:a]
			o = 1 - o
		return int(x == y)


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		copymat = mat.copy()

		def rotr(x):
			temp = x.copy()
			temp = temp[1:]
			temp.append(x[0])
			return temp

		def rotl(x):
			temp = x[0:len(x) - 1]
			temp.insert(0, x[len(x) - 1])
			return temp
		for i in range(n):
			if (i + 1) % 2 == 0:
				for j in range(x):
					mat[i] = rotr(mat[i])
			else:
				for j in range(x):
					mat[i] = rotl(mat[i])
		if copymat == mat:
			return 1
		else:
			return 0


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		if x % m == 0:
			return 1
		else:
			for i in range(n):
				for j in range(m):
					if mat[i][j] != mat[i][(j + x) % m]:
						return 0
			return 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, m) = [int(x) for x in input().split()]
		mat = [[0] * m for x in range(n)]
		arr = input().split()
		for i in range(n * m):
			mat[i // m][i % m] = int(arr[i])
		x = int(input())
		ob = Solution()
		print(ob.isSuperSimilar(n, m, mat, x))


class Solution:

	def swap(mat, inx, start, end):
		while start < end:
			(mat[inx][start], mat[inx][end]) = (mat[inx][end], mat[inx][start])
			start += 1
			end -= 1

	def isSuperSimilar(self, n, m, mat, d):
		chk = []
		for i in range(n):
			tmp = []
			for j in range(m):
				tmp.append(mat[i][j])
			chk.append(tmp)
		d %= m
		for i in range(n):
			if i % 2 == 0:
				Solution.swap(mat, i, 0, d - 1)
				Solution.swap(mat, i, d, m - 1)
				Solution.swap(mat, i, 0, m - 1)
			else:
				Solution.swap(mat, i, 0, m - 1)
				Solution.swap(mat, i, 0, d - 1)
				Solution.swap(mat, i, d, m - 1)
		if chk == mat:
			return 1
		return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, m) = [int(x) for x in input().split()]
		mat = [[0] * m for x in range(n)]
		arr = input().split()
		for i in range(n * m):
			mat[i // m][i % m] = int(arr[i])
		x = int(input())
		ob = Solution()
		print(ob.isSuperSimilar(n, m, mat, x))


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		x1 = x % m
		for i in range(n):
			for j in range(m):
				if i % 2 == 0:
					j1 = (j + x) % m
				else:
					j1 = (j - x) % m
				if mat[i][j1] != mat[i][j]:
					return 0
		return 1


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		x = x % m
		if x == 0:
			return 1
		for i in range(n):
			if i % 2 == 0:
				y = mat[i][m - x:] + mat[i][:m - x]
				if y != mat[i]:
					return 0
			else:
				y = mat[i][x:] + mat[i][:m - x]
				if y != mat[i]:
					return 0
		return 1


class Solution:

	def isSuperSimilar(self, n, m, mat, x):

		def rotate(row, x):
			x %= len(row)
			rotated_row = row + row
			return rotated_row[x:x + len(row)]

		def check(mat1, mat2):
			if mat1 == mat2:
				return 1
			else:
				return 0
		mat2 = []
		for i in range(n):
			mat2.append(rotate(mat[i], x))
		return check(mat, mat2)


import itertools

class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		x = x % m
		newmat = []
		for i in range(0, n):
			temp = list(itertools.repeat(0, m))
			newmat.append(temp)
		for i in range(0, n):
			for j in range(0, m):
				newmat[i][j] = mat[i][j]
		for i in range(0, n):
			for k in range(0, x):
				if i % 2 == 0:
					temp = mat[i][0]
					for j in range(1, m):
						mat[i][j - 1] = mat[i][j]
					mat[i][m - 1] = temp
				else:
					temp = mat[i][m - 1]
					for j in range(0, m - 1):
						mat[i][j + 1] = mat[i][j]
					mat[i][0] = temp
		for i in range(0, n):
			for j in range(0, m):
				if mat[i][j] != newmat[i][j]:
					return 0
		return 1


class Solution:

	def isSuperSimilar(self, n, m, mat, x):

		def rotate_row(index, row, x):
			x = x % len(row)
			rortated_row = row + row
			return rortated_row[x:len(row) + x]

		def matrix_similaruty(mat1, mat2):
			if mat1 == mat2:
				return 1
			else:
				return 0
		mat2 = []
		for i in range(n):
			mat2.append(rotate_row(i, mat[i], x))
		return matrix_similaruty(mat, mat2)


class Solution:

	def swap(self, mat, i, j1, j2):
		while j1 < j2:
			(mat[i][j1], mat[i][j2]) = (mat[i][j2], mat[i][j1])
			j1 += 1
			j2 -= 1

	def isSuperSimilar(self, n, m, mat, x):
		check = []
		for i in range(n):
			temp = []
			for j in range(m):
				temp.append(mat[i][j])
			check.append(temp)
		x = x % m
		for i in range(n):
			if i % 2 == 0:
				self.swap(mat, i, 0, x - 1)
				self.swap(mat, i, x, m - 1)
				self.swap(mat, i, 0, m - 1)
			else:
				self.swap(mat, i, 0, m - 1)
				self.swap(mat, i, 0, x - 1)
				self.swap(mat, i, x, m - 1)
		if check == mat:
			return 1
		return 0


class Solution:
	RIGHT = 'RIGHT'
	LEFT = 'LEFT'

	def isSuperSimilar(self, n, m, mat, x):
		smat = [[0 for i in range(m)] for j in range(n)]
		for i in range(n):
			if i % 2 == 0:
				smat[i] = self.rotateRow(mat[i], x, m, Solution.LEFT)
			else:
				smat[i] = self.rotateRow(mat[i], x, m, 'right')
		for i in range(n):
			for j in range(m):
				if mat[i][j] != smat[i][j]:
					return 0
		return 1

	def rotateRow(self, row, x, m, d):
		r = []
		if d == Solution.LEFT:
			r.extend(row[x % m:])
			r.extend(row[:x % m])
		else:
			r.extend(row[m - x % m:])
			r.extend(row[:m - x % m])
		return r


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		if x % m == 0:
			return 1
		x %= m
		for i in range(0, n):
			isEven = i % 2 == 0
			for j in range(0, m):
				if isEven:
					temp = j - x
					if temp < 0:
						temp = m + temp
				else:
					temp = j + x
					if temp >= m:
						temp = temp % m
				if mat[i][temp] != mat[i][j]:
					return 0
		return 1


import numpy as np

def r(n, m, row, x):
	row1 = [0 for i in range(m)]
	x = x % m
	row1[0:m - x] = row[x:x + m - x]
	row1[m - x:m] = row[0:x]
	return row1

def l(n, m, row, x):
	row1 = [0 for i in range(m)]
	x = x % m
	row1[0:x] = row[m - x:m]
	row1[x:m] = row[0:m - x]
	return row1

def same(mat1, mat2, n, m):
	for i in range(n):
		for j in range(m):
			if mat1[i][j] != mat2[i][j]:
				return 0
	return 1

class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		res = [[0 for i in range(m)] for j in range(n)]
		for i in range(n):
			if i % 2 == 0:
				res[i] = l(n, m, mat[i], x)
			else:
				res[i] = r(n, m, mat[i], x)
		return same(mat, res, n, m)


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		x = x % m
		if x == 0:
			return 1
		for i in range(n):
			if i % 2 == 0:
				op = -x
			else:
				op = x
			for j in range(m):
				new_j = (j + op) % m
				if mat[i][j] != mat[i][new_j]:
					return 0
		return 1


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		oa = []
		if m == 1:
			return 1
		(evenR, oddR) = ([], [])
		for i in range(n):
			oa.extend(mat[i])
			if i % 2 == 0:
				evenR.append(mat[i])
			else:
				oddR.append(mat[i])
		for i in range(x):
			for j in range(len(evenR)):
				evenR[j] = [evenR[j][-1]] + evenR[j][:-1]
			for j in range(len(oddR)):
				oddR[j] = oddR[j][1:] + [oddR[j][0]]
		x = len(evenR)
		y = len(oddR)
		(i, j) = (0, 0)
		res = []
		while i < x or j < y:
			if i < x:
				res.extend(evenR[i])
				i += 1
			if j < y:
				res.extend(oddR[j])
				j += 1
		if res == oa:
			return 1
		else:
			return 0


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		if x == 0 or x % m == 0:
			return 1
		for i in range(n):
			direction = -1 if i % 2 == 0 else 1
			for j in range(m):
				new_idx = j - direction * x
				while new_idx >= m:
					new_idx -= m
				while new_idx < 0:
					new_idx += m
				if mat[i][j] != mat[i][new_idx]:
					return 0
		return 1


class Solution:

	def isSuperSimilar(self, n, m, mat, X):
		for i in range(n):
			if i % 2:
				temp1 = [-1] * m
				for j in range(m):
					if mat[i][(j + X) % m] != mat[i][j]:
						return 0
			else:
				temp2 = [-1] * m
				x = abs(m - X)
				for j in range(m):
					if mat[i][(j + x) % m] != mat[i][j]:
						return 0
		return 1


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		if x == 0 or x % m == 0:
			return 1
		if x % 2 == 1 or m % 2 == 1:
			for i in mat:
				if i != m * [i[0]]:
					return 0
		else:
			for i in mat:
				if i != [i[0], i[1]] * int(m / 2):
					return 0
		return 1


class Solution:

	def rotateL(self, arr, x):
		n = len(arr)
		temp = arr[:]
		for i in range(n):
			arr[i] = temp[(i + x) % n]
		return temp == arr

	def rotateR(self, arr, x):
		n = len(arr)
		temp = arr[:]
		for i in range(n):
			arr[i] = temp[(i - x) % n]
		return temp == arr

	def isSuperSimilar(self, n, m, mat, x):
		for i in range(0, n, 2):
			if not self.rotateL(mat[i], x):
				return 0
		for i in range(1, n, 2):
			if not self.rotateR(mat[i], x):
				return 0
		return 1


import copy

class Solution:

	def isSuperSimilar(self, n, m, a, x):
		x = x % m
		for i in range(n):
			for j in range(m - 1):
				if a[i][j] != a[i][(j - x + m) % m]:
					return 0
		return 1
		for i in range(n):
			for j in range(m):
				if arr[i][j] != a[i][j]:
					return 0
		return 1


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		for i in range(n):
			row = mat[i]
			new_row = self.rotate(i, x, row)
			if row != new_row:
				return 0
		return 1

	def rotate(self, n, times, row):
		if times > 0:
			while times > 0:
				if n % 2 != 0:
					temp = row[1:]
					ele = row[0]
					temp.append(ele)
					row = temp
				else:
					temp = row[:-1]
					ele = row[-1]
					temp.insert(0, ele)
					row = temp
				times = times - 1
		return row


from copy import deepcopy

class Solution:

	def isSuperSimilar(self, n, m, mat, x):

		def rightrotate(arr, k):
			k = k % len(arr)
			n = len(arr) - k
			arr[:n] = arr[:n][::-1]
			arr[n:] = arr[n:][::-1]
			arr[:] = arr[::-1]

		def leftrotate(arr, k):
			k = k % len(arr)
			arr[:k] = arr[:k][::-1]
			arr[k:] = arr[k:][::-1]
			arr[:] = arr[::-1]
		cpy = deepcopy(mat)
		for i in range(n):
			if i & 1 == 0:
				rightrotate(mat[i], x)
			else:
				leftrotate(mat[i], x)
		if mat == cpy:
			return 1
		return 0


import numpy

class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		z = []
		for i in range(len(mat)):
			if i % 2 == 0:
				f = numpy.roll(mat[i], -x)
				z.append(list(f))
			else:
				f1 = numpy.roll(mat[i], x)
				z.append(list(f1))
		if z == mat:
			return 1
		else:
			return 0


def rotate_right(arr, x):
	x = x % len(arr)
	return arr[len(arr) - x:] + arr[:len(arr) - x]

def rotate_left(arr, x):
	x = x % len(arr)
	return arr[x:] + arr[:x]

def mgc(mat, x):
	temp = []
	for i in range(len(mat)):
		if i % 2 == 0:
			temp.append(rotate_left(mat[i], x))
		else:
			temp.append(rotate_right(mat[i], x))
	for i in range(len(mat)):
		for j in range(len(mat[0])):
			if mat[i][j] != temp[i][j]:
				return 0
	return 1

class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		return mgc(mat, x)


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		for i in range(n):
			new_x = x % m
			row = mat[i]
			if i % 2 == 0:
				mat[i] = row[new_x:] + row[:new_x]
			else:
				mat[i] = row[-1 * new_x:] + row[:-1 * new_x]
			if mat[i] == row:
				pass
			else:
				return 0
		return 1


import copy

class Solution:

	def isSuperSimilar(self, n, m, a, x):
		x %= m
		if x == 0:
			return 1
		t = 0
		y = 0
		b = [i[:] for i in a]
		for i in range(n):
			p = x
			for j in range(m):
				while i % 2 == 0 and p > 0:
					t = b[i].pop()
					b[i].insert(0, t)
					p -= 1
				while i % 2 != 0 and p > 0:
					t = b[i].pop(0)
					b[i].append(t)
					p -= 1
				if a[i] == b[i]:
					y += 1
		return 1 if y == n else 0


class Solution:

	def rotate_right(self, row, x):
		n = len(row)
		end = n - 1
		j = 0
		while j != x:
			temp = row[0]
			for i in range(n - 1):
				row[i] = row[i + 1]
			row[end] = temp
			j += 1
		return row

	def rotate_left(self, row, x):
		n = len(row)
		end = n - 1
		j = 0
		while j != x:
			repl = row[end]
			temp = row[0]
			for i in range(n - 1):
				temp1 = temp
				temp = row[i + 1]
				row[i + 1] = temp1
			row[0] = repl
			j += 1
		return row

	def isSuperSimilar(self, n, m, mat, x):
		mat1 = [list(row) for row in mat]
		for i in mat:
			if mat.index(i) % 2 == 0:
				self.rotate_left(i, x)
			else:
				self.rotate_right(i, x)
		if mat1 == mat:
			return 1
		else:
			return 0


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		pos = 1
		for i in range(n):
			for j in range(m):
				if mat[i][(j + x) % m] != mat[i][j]:
					pos = 0
					break
		return pos


from copy import deepcopy

class Solution:

	def reverseIt(self, arr, l, r):
		while l <= r:
			temp = arr[l]
			arr[l] = arr[r]
			arr[r] = temp
			l += 1
			r -= 1
		return arr

	def leftRotate(self, k, arr):
		if k >= len(arr):
			k = k % len(arr)
		arr = self.reverseIt(arr, 0, k - 1)
		arr = self.reverseIt(arr, k, len(arr) - 1)
		return self.reverseIt(arr, 0, len(arr) - 1)

	def rightRotate(self, k, arr):
		if k >= len(arr):
			k = k % len(arr)
		arr = self.reverseIt(arr, len(arr) - k, len(arr) - 1)
		arr = self.reverseIt(arr, 0, len(arr) - k - 1)
		return self.reverseIt(arr, 0, len(arr) - 1)

	def isSuperSimilar(self, n, m, matrix, x):
		orignal = []
		orignal = deepcopy(matrix)
		rows = n
		for i in range(rows):
			if i % 2 == 0:
				matrix[i] = self.leftRotate(x, matrix[i])
			else:
				matrix[i] = self.rightRotate(x, matrix[i])
		if orignal == matrix:
			return 1
		else:
			return 0


class Solution:

	def isSuperSimilar(self, n, m, mat, x):
		temp = []
		for i in range(n):
			p = []
			for j in range(m):
				p.append(mat[i][j])
			temp.append(p)
		for i in range(n):
			if i % 2 != 0:
				for j in range(m):
					temp[i][j] = mat[i][(m - x + j) % m]
			else:
				for j in range(m):
					temp[i][j] = mat[i][(j + x) % m]
		c = 0
		for i in range(n):
			for j in range(m):
				if mat[i][j] == temp[i][j]:
					c = c + 1
		if c == n * m:
			return 1
		else:
			return 0