Welcome to Sevenkplus' perfect math class! In this class we will study an algebraic structure called magma. 

A magma is a nonempty set ${M}$ equipped with a binary operation ${\large{\odot}}:M\times M\rightarrow M$. We write $x\mbox{\large{\odot}}y$ for the application of the operator on the two elements $x,y\in M$.
Note that there are no restrictions on the binary operation. For example, we cannot assume that $(x\text{\large{\odot}}y)\text{}z=\large{\odot}x\text{\large{\odot}}(y\text{\large{\odot}}z)$ always holds.

There are many different types of magmas. Some are interesting, others are even more interesting. Studying specific types of magmas is an important part of mathematics.
Below we introduce the following types of magmas.

A quasigroup is a magma such that for all $x,y\in M$, there exists a unique $z\in M$ such that $unrecognized$ and a unique ${w\in M}$ such that $w\text{\large{\odot}}x=y$.

A loop is a quasigroup such that there is a unique element ${e\in M}$ such that for all $x\in{M}$, $e\large{\odot} x=x\large{\odot} e=x$.

A semigroup is a magma such that for all $x,y,z\in M$, we have $(x\text{\large{\odot}}y)\text{\large{\odot}}z=x\text{\large{\odot}}(y\text{\large{\odot}}z)$.

A monoid is a semigroup such that there is a uniqe element ${e\in M}$ such that for all $x\in{M}$, $e\large{\odot} x=x\large{\odot} e=x$.

A group is a monoid such that for all $x\in\textit{M}$, there exists $y\in M$ such that $x\large{\odot} y=y\large{\odot} x=e$.

An abelian group is a group such that for all $x,y\in M$, we have $x\text{\large{\odot}}y=y\text{\large{\odot}}x$.

A rack is a magma such that (1) for all $x,y,z\in M$, we have $x\text{\large{\odot}}(y\text{\large{\odot}}z)=(x\text{\large{\odot}}y)\text{\large{\odot}}(x\text{\large{\odot}}z)$ and (2) for all $x,y\in M$, there exists a unique $z\in M$ such that $x\text{\large{\odot}}z=y$.

A quandle is a rack such that for all $x\in\textit{M}$, we have $x\text{\large{\odot}}x=x$.

In this problem, you are given several magmas. You have to tell us what types they are.

Input Format

The first line is a integer ${T}$, the number of magmas given to you.
Following are ${T}$ magmas.

For each magma, the first line is an integer $n$, the size of the set ${M}$. (Yes, you only need to consider finite algebraic structures here, which greatly simplifies the problem.)
Without loss of generality, we assume that $M=\{0,1,\large{\odot},n-1\}$.

Following are $n$ lines. Each line contains $n$ space-separated integers. The $j$-th number on the ${i}$-th line is $(i-1)\text{\large{\odot}}(j-1)$ where $0$ is the binary operation of the magma.

Constraints  

$1\leq T\leq60$ 

$1\leq n\leq110$. 

Output Format

For each magma, output one line, which is the magic number  of the magma (denoted by ${S}$ henceforth).

The magic number ${S}$ of a magma is defined as:

Initially, let $S=0$.
If the magma is a quasigroup, add ${1}$ to ${S}$.
If the magma is a loop, add $2$ to ${S}$.
If the magma is a semigroup, add ${4}$ to ${S}$.
If the magma is a monoid, add $8$ to ${S}$.
If the magma is a group, add ${16}$ to ${S}$.
If the magma is an abelian group, add $32$ to ${S}$.
If the magma is a rack, add ${64}$ to ${S}$.
If the magma is a quandle, add ${128}$ to ${S}$.
Then ${S}$ is the magic number of the magma.

Sample Input
2
1
0
2
1 1
1 0

Sample Output
255
0

Explanation

The first magma satisfies all rules while the second one satisfies none.

Source: hackerrank | Difficulty: MEDIUM
Tags: Matrices


Solutions:
def isDivisible(M):
	N = len(M)
	return min((len({M[x][z] for z in range(N)}) for x in range(N))) == N == min((len({M[z][x] for z in range(N)}) for x in range(N)))

def getIdentity(M):
	for e in range(len(M)):
		for x in range(len(M)):
			if M[e][x] == x == M[x][e]:
				continue
			else:
				break
		else:
			return e
	return None

def isAssociative(M):
	N = len(M)
	for a in range(N):
		for b in range(N):
			for c in range(N):
				if M[a][M[b][c]] != M[M[a][b]][c]:
					return False
	return True

def invertsTo(M, e):
	N = len(M)
	for x in range(N):
		for y in range(N):
			if M[x][y] == M[y][x] == e:
				break
		else:
			return False
	return True

def isCommutative(M):
	for i in range(len(M)):
		for j in range(i + 1, len(M)):
			if M[i][j] != M[j][i]:
				return False
	return True

def autoInversion(M):
	for x in range(len(M)):
		if M[x][x] != x:
			return False
	return True

def isRack(M):
	N = len(M)
	left = min((len({M[x][z] for z in range(N)}) for x in range(N))) == N
	if not left:
		return False
	for a in range(N):
		for b in range(N):
			for c in range(N):
				if M[a][M[b][c]] != M[M[a][b]][M[a][c]]:
					return False
	return True
M = [[0, 0, 0, 0, 0], [2, 1, 1, 1, 1], [1, 2, 2, 2, 2], [4, 4, 4, 3, 3], [3, 3, 3, 4, 4]]
M = [[1, 3, 2, 5, 4], [1, 2, 3, 5, 4], [1, 2, 3, 5, 4], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]]

def magicNumber(M):
	divides = isDivisible(M)
	identity = getIdentity(M)
	has_identity = identity != None
	inverts = has_identity and invertsTo(M, identity)
	associates = isAssociative(M)
	auto_inverts = autoInversion(M)
	commutes = isCommutative(M)
	quasigroup = divides
	loop = divides and has_identity
	semigroup = associates
	monoid = associates and has_identity
	group = divides and associates and inverts and has_identity
	abelian_group = group and commutes
	rack = isRack(M)
	quandle = rack and auto_inverts
	number = [quasigroup, loop, semigroup, monoid, group, abelian_group, rack, quandle]
	n = 0
	while number:
		n = 2 * n + number.pop()
	return n
num_cases = int(input())
for case in range(num_cases):
	N = int(input())
	M = [list(map(int, input().split())) for i in range(N)]
	print(magicNumber(M))


import itertools

def isQuasiGroup(M):
	n = len(M)
	for x in range(n):
		if len({M[x][z] for z in range(n)}) != n or len({M[w][x] for w in range(n)}) != n:
			return False
	return True

def getIdentity(M):
	n = len(M)
	for e in range(n):
		if sum((1 for x in range(n) if M[e][x] == x and M[x][e] == x)) == n:
			return e
	return None

def isLoop(M):
	return isQuasiGroup(M) and getIdentity(M) != None

def isSemiGroup(M):
	n = len(M)
	for (x, y, z) in itertools.product(range(n), repeat=3):
		if M[M[x][y]][z] != M[x][M[y][z]]:
			return False
	return True

def isMonoid(M):
	return isSemiGroup(M) and isLoop(M)

def isInversible(M, e):
	for x in range(n):
		if sum((1 for y in range(n) if M[x][y] == e and M[y][x] == e)) < 1:
			return False
	return True

def isGroup(M):
	e = getIdentity(M)
	return isMonoid(M) and isInversible(M, e)

def isCommutative(M):
	n = len(M)
	for (x, y) in itertools.product(range(n), repeat=2):
		if M[x][y] != M[y][x]:
			return False
	return True

def isAbelianGroup(M):
	return isGroup(M) and isCommutative(M)

def isRack(M):
	n = len(M)
	for x in range(n):
		if len({M[x][z] for z in range(n)}) != n:
			return False
	for (x, y, z) in itertools.product(range(n), repeat=3):
		if M[x][M[y][z]] != M[M[x][y]][M[x][z]]:
			return False
	return True

def isAutoInvert(M):
	n = len(M)
	for x in range(n):
		if M[x][x] != x:
			return False
	return True

def isQuandle(M):
	return isRack(M) and isAutoInvert(M)

def solve(M):
	quasiGroup = isQuasiGroup(M)
	e = getIdentity(M)
	loop = quasiGroup and e != None
	semiGroup = isSemiGroup(M)
	monoid = semiGroup and e != None
	group = monoid and isInversible(M, e)
	abelianGroup = group and isCommutative(M)
	rack = isRack(M)
	quandle = rack and isAutoInvert(M)
	S = 0
	if quasiGroup:
		S += 1
	if loop:
		S += 2
	if semiGroup:
		S += 4
	if monoid:
		S += 8
	if group:
		S += 16
	if abelianGroup:
		S += 32
	if rack:
		S += 64
	if quandle:
		S += 128
	return S
T = int(input())
for _ in range(T):
	n = int(input())
	M = list((list((int(_) for _ in input().split())) for _ in range(n)))
	print(solve(M))


def identity(dot, n):
	for e in range(n):
		if all((x == dot[e][x] == dot[x][e] for x in range(n))):
			return e
	return None
for _ in range(int(input())):
	n = int(input())
	dot = [[]] * n
	for i in range(n):
		dot[i] = list(map(int, input().split()))
	is_quasigroup = all((all((any((dot[x][z] == y for z in range(n))) and any((dot[w][x] == y for w in range(n))) for y in range(n))) for x in range(n)))
	e = identity(dot, n)
	is_loop = is_quasigroup and e is not None
	is_semigroup = all((all((all((dot[dot[x][y]][z] == dot[x][dot[y][z]] for z in range(n))) for y in range(n))) for x in range(n)))
	is_monoid = is_semigroup and e is not None
	is_group = is_monoid and all((any((e == dot[x][y] == dot[y][x] for y in range(n))) for x in range(n)))
	is_abelian_group = is_group and all((all((dot[x][y] == dot[y][x] for y in range(n))) for x in range(n)))
	is_rack = all((all((all((dot[x][dot[y][z]] == dot[dot[x][y]][dot[x][z]] for z in range(n))) for y in range(n))) for x in range(n))) and all((all((any((dot[x][z] == y for z in range(n))) for y in range(n))) for x in range(n)))
	is_quandle = is_rack and all((dot[x][x] == x for x in range(n)))
	print(is_quasigroup + 2 * is_loop + 4 * is_semigroup + 8 * is_monoid + 16 * is_group + 32 * is_abelian_group + 64 * is_rack + 128 * is_quandle)


def quasigroup(n, l):
	s = set([int(i) for i in range(n)])
	for i in range(n):
		if set(l[i]) != s:
			return False
	for i in range(n):
		l_2 = [-1 for j in range(n)]
		for j in range(n):
			l_2[j] = l[j][i]
		if set(l_2) != s:
			return False
	return True

def loop(n, l):
	e = -1
	for i in range(n):
		flag = 1
		for j in range(n):
			if l[i][j] != j:
				flag = 0
				break
		if flag == 1:
			e = i
	if e == -1:
		return False
	flag = 1
	for i in range(n):
		if l[i][e] != i:
			flag = 0
			break
	return flag > 0

def semigroup(n, l):
	for i in range(n):
		for j in range(n):
			for k in range(n):
				if l[l[i][j]][k] != l[i][l[j][k]]:
					return False
	return True

def monoid(n, l):
	e = -1
	for i in range(n):
		flag = 1
		for j in range(n):
			if l[i][j] != j:
				flag = 0
				break
		if flag == 1:
			e = i
	if e == -1:
		return [False, -1]
	flag = 1
	for i in range(n):
		if l[i][e] != i:
			flag = 0
			break
	return [flag > 0, e]

def group(n, l, e):
	flag = 1
	for i in range(n):
		flag_2 = 0
		for j in range(n):
			if l[i][j] == e and l[j][i] == e:
				flag_2 = 1
				break
		if flag_2 == 0:
			flag = 0
			break
	return flag > 0

def abelian(n, l):
	flag = 1
	for i in range(n - 1):
		for j in range(i + 1, n):
			if l[i][j] != l[j][i]:
				flag = 0
				break
		if flag == 0:
			break
	return flag > 0

def rack(n, l):
	for i in range(n):
		for j in range(n):
			for k in range(n):
				if l[i][l[j][k]] != l[l[i][j]][l[i][k]]:
					return False
	s = set([int(i) for i in range(n)])
	for i in range(n):
		if set(l[i]) != s:
			return False
	return True

def quandle(n, l):
	for i in range(n):
		if l[i][i] != i:
			return False
	return True
t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	l = [[0 for i in range(n)] for j in range(n)]
	for i in range(n):
		l[i] = [int(j) for j in input().split()]
	if n == 1:
		print('255')
		continue
	total = 0
	if quasigroup(n, l):
		total += 1
		if loop(n, l):
			total += 2
	if semigroup(n, l):
		total += 4
		if monoid(n, l)[0]:
			total += 8
			e = monoid(n, l)[1]
			if group(n, l, e):
				total += 16
				if abelian(n, l):
					total += 32
	if rack(n, l):
		total += 64
		if quandle(n, l):
			total += 128
	print(total)


def is_quasigroup(N, op):
	rN = range(N)
	test = True
	for x in rN:
		if len(set(op[x][:])) != N:
			test = False
			break
	if test:
		for y in rN:
			if len(set([op[i][y] for i in rN])) != N:
				test = False
				break
	return test

def unit(N, op):
	rN = range(N)
	rNl = list(rN)
	u = -1
	while len(rNl) > 0:
		e = rNl.pop()
		if all([op[e][x] == x and op[x][e] == x for x in rN]) == True:
			u = e
			break
	return u

def is_loop(N, op):
	rN = range(N)
	test = is_quasigroup(N, op)
	if test:
		u = unit(N, op)
		if u == -1:
			test = False
	return test

def is_semigroup(N, op):
	rN = range(N)
	test = True
	for x in rN:
		for y in rN:
			for z in rN:
				if op[op[x][y]][z] != op[x][op[y][z]]:
					test = False
					break
			if test == False:
				break
		if test == False:
			break
	return test

def is_monoid(N, op):
	rN = range(N)
	test = is_semigroup(N, op)
	if test:
		u = unit(N, op)
		if u == -1:
			test = False
	return test

def is_group(N, op):
	test = is_quasigroup(N, op) and is_monoid(N, op)
	return test

def is_abelian(N, op):
	rN = range(N)
	test = is_group(N, op)
	if test == True:
		for x in rN:
			for y in rN:
				if op[x][y] != op[y][x]:
					test = False
					break
			if test == False:
				break
	return test

def is_rack(N, op):
	rN = range(N)
	test = True
	for x in rN:
		if len(set(op[x][:])) != N:
			test = False
			break
	if test:
		for x in rN:
			for y in rN:
				for z in rN:
					if op[x][op[y][z]] != op[op[x][y]][op[x][z]]:
						test = False
						break
				if test == False:
					break
			if test == False:
				break
	return test

def is_quandle(N, op):
	rN = range(N)
	test = is_rack(N, op)
	if test == True:
		for x in rN:
			if op[x][x] != x:
				test = False
				break
	return test
T = int(input().strip())
for _ in range(T):
	N = int(input().strip())
	OP = []
	for t in range(N):
		op_t = [int(i) for i in input().strip().split(' ')]
		OP.append(op_t)
	S = 0
	if is_quasigroup(N, OP) == True:
		S += 1
	if is_loop(N, OP) == True:
		S += 2
	if is_semigroup(N, OP) == True:
		S += 4
	if is_monoid(N, OP) == True:
		S += 8
	if is_group(N, OP) == True:
		S += 16
	if is_abelian(N, OP) == True:
		S += 32
	if is_rack(N, OP) == True:
		S += 64
	if is_quandle(N, OP) == True:
		S += 128
	print(S)


T = int(input())
for t in range(T):
	n = int(input())
	A = []
	for _ in range(n):
		A.append(tuple(map(int, input().split(' '))))
	At = tuple(zip(*A))
	A = tuple((row for row in A))
	S = 0
	symm = A == At
	right_inv = all((len(set(row)) == n for row in A))
	if symm:
		left_inv = True
	else:
		left_inv = all((len(set(col)) == n for col in At))
	canonical_rows = [r for (r, row) in enumerate(A) if row == tuple(range(n))]
	identity = False
	if len(canonical_rows) == 1:
		if At[canonical_rows[0]] == tuple(range(n)):
			identity = True
	if right_inv and left_inv:
		S += 1
		if identity:
			S += 2
	ass = all((A[A[x][y]][z] == A[x][A[y][z]] for x in range(n) for y in range(n) for z in range(n)))
	if ass:
		S += 4
		if identity:
			S += 8
			if right_inv and left_inv:
				S += 16
				if symm:
					S += 32
	rack_1 = all((A[x][A[y][z]] == A[A[x][y]][A[x][z]] for x in range(n) for y in range(n) for z in range(n)))
	if right_inv and rack_1:
		S += 64
		quandle = all((A[x][x] == x for x in range(n)))
		if quandle:
			S += 128
	print(S)


def isQuasi(A):
	F = [False] * len(A)
	for x in range(len(A)):
		for y in range(len(A)):
			z = A[x][y]
			if F[z]:
				return False
			F[z] = True
		for y in range(len(A)):
			z = A[y][x]
			if not F[z]:
				return False
			F[z] = False
	return True

def findIdent(A):
	id = -1
	for e in range(len(A)):
		for x in range(len(A)):
			if A[e][x] != x or A[x][e] != x:
				break
		else:
			id = e
	return id

def isSemi(A):
	for x in range(len(A)):
		Ax = A[x]
		for y in range(len(A)):
			Ay = A[y]
			Axy = A[Ax[y]]
			for z in range(len(A)):
				if Axy[z] != Ax[Ay[z]]:
					return False
	return True

def isGroup(A, e):
	for x in range(len(A)):
		for y in range(len(A)):
			if A[x][y] == e and A[y][x] == e:
				break
		else:
			return False
	return True

def isAbelian(A):
	for x in range(len(A)):
		for y in range(len(A)):
			if A[x][y] != A[y][x]:
				return False
	return True

def isRack(A):
	for x in range(len(A)):
		for y in range(len(A)):
			n = 0
			for z in range(len(A)):
				if A[x][A[y][z]] != A[A[x][y]][A[x][z]]:
					return False
				if A[x][z] == y:
					n += 1
			if n != 1:
				return False
	return True

def isQuandle(A):
	for i in range(len(A)):
		if A[i][i] != i:
			return False
	return True
T = int(input())
for t in range(T):
	n = int(input())
	A = []
	for i in range(n):
		A.append([int(x) for x in input().split()])
	S = 0
	id = findIdent(A)
	if isQuasi(A):
		S += 1
		if id >= 0:
			S += 2
	if isSemi(A):
		S += 4
		if id >= 0:
			S += 8
			if isGroup(A, id):
				S += 16
				if isAbelian(A):
					S += 32
	if isRack(A):
		S += 64
		if isQuandle(A):
			S += 128
	print(S)


def quasi(n, M, A):
	for i in range(n):
		if len(set(M[i])) != len(M[i]) or len(set(A[i])) != len(A[i]):
			return False
	return True

def vectorizer(n):
	return [j for j in range(n)]

def loop(n, M, A):
	v = vectorizer(n)
	for i in range(n):
		if v == M[i] and v == A[i]:
			return True
	return False

def semigroup(n, M):
	for i in range(n):
		for j in range(n):
			for k in range(n):
				if M[i][M[j][k]] != M[M[i][j]][k]:
					return False
	return True

def monoid(n, M, A):
	v = vectorizer(n)
	for i in range(n):
		if v == M[i] and v == A[i]:
			return i
	return -1

def group(n, M, e):
	for i in range(n):
		if not e in M[i]:
			return False
	return True

def abel(n, M):
	for i in range(n):
		for j in range(n):
			if M[i][j] != M[j][i]:
				return False
	return True

def rack(n, M):
	for i in range(n):
		for j in range(n):
			t = True
			for k in range(n):
				if M[i][M[j][k]] != M[M[i][j]][M[i][k]]:
					return False
				if M[i][k] == j:
					t = False
			if t:
				return False
	return True

def quandle(n, M):
	for i in range(n):
		if M[i][i] != i:
			return False
	return True

def calculate(n, M, A):
	s = 0
	if quasi(n, M, A):
		s = s + 1
		if loop(n, M, A):
			s = s + 2
	if semigroup(n, M):
		s = s + 4
		e = monoid(n, M, A)
		if e >= 0:
			s = s + 8
			if group(n, M, e):
				s = s + 16
				if abel(n, M):
					s = s + 32
	if rack(n, M):
		s = s + 64
		if quandle(n, M):
			s = s + 128
	return s

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = []
		B = []
		for i in range(n):
			b = [int(x) for x in input().split()]
			a.append(b)
		for i in range(n):
			B.append([])
			for j in range(n):
				B[i].append(a[j][i])
		print(calculate(n, a, B))
		T -= 1
main()


T = int(input())
for _ in range(T):
	n = int(input())
	table = [list(map(int, input().split())) for i in range(n)]
	tabletranspose = [[table[j][i] for j in range(n)] for i in range(n)]
	quasigp = all([len(set(x)) == n for x in table]) and all([len(set(x)) == n for x in tabletranspose])
	b = list(range(n)) in table and list(range(n)) in tabletranspose
	loop = b * quasigp
	semigp = True
	for i in range(n):
		for j in range(i + 1):
			for k in range(j + 1):
				semigp = semigp and table[i][table[j][k]] == table[table[i][j]][k]
	monoid = semigp * b
	group = monoid * quasigp
	abelian = group * (table == tabletranspose)
	rack = all([len(set(x)) == n for x in table])
	for i in range(n):
		for j in range(i + 1):
			for k in range(j + 1):
				rack = rack and table[i][table[j][k]] == table[table[i][j]][table[i][k]]
	quandle = rack * all([table[i][i] == i for i in range(n)])
	print(quasigp + 2 * loop + 4 * semigp + 8 * monoid + 16 * group + 32 * abelian + 64 * rack + 128 * quandle)


def quasigroup(n, data, RN):
	(H, V) = ([-1] * n, [-1] * n)
	for i in RN:
		for j in RN:
			if V[data[i][j]] == i or H[data[j][i]] == i:
				return False
			V[data[i][j]] = i
			H[data[j][i]] = i
	return True

def loop(n, data, RN):
	for i in RN:
		j = 0
		while j < n:
			if data[i][j] != j or data[j][i] != j:
				break
			j += 1
		if j == n:
			return i
	return -1

def semigroup(n, data, RN):
	for i in RN:
		for j in RN:
			for k in RN:
				if data[data[i][j]][k] != data[i][data[j][k]]:
					return False
	return True

def monoid(n, data, RN):
	for k in RN:
		i = 0
		while i < n:
			if data[i][k] != i or data[k][i] != i:
				break
			i += 1
		if i == n:
			return True
	return False

def group(n, data, RN, lp):
	for i in RN:
		j = 0
		while j < n:
			if data[i][j] == lp and data[j][i] == lp:
				j = 10000
			j += 1
		if j < 10000:
			return False
	return True

def abelianGroup(n, data, RN):
	for i in RN:
		for j in RN:
			if data[i][j] != data[j][i]:
				return False
	return True

def rack(n, data, RN):
	for i in RN:
		for j in RN:
			f = False
			for k in RN:
				if data[i][data[j][k]] != data[data[i][j]][data[i][k]]:
					return False
				if not f and data[i][k] == j:
					f = True
			if not f:
				return False
	return True

def quandle(n, data, RN):
	for i in RN:
		if data[i][i] != i:
			return False
	return True

def solution(n, data):
	(S, RN) = (0, range(n))
	if quasigroup(n, data, RN):
		S |= 1
	if S & 1:
		lp = loop(n, data, RN)
		if lp >= 0:
			S |= 2
	if semigroup(n, data, RN):
		S |= 4
	if S & 4 == 4 and monoid(n, data, RN):
		S |= 8
	if S & 10 == 10 and group(n, data, RN, lp):
		S |= 16
	if S & 16 and abelianGroup(n, data, RN):
		S |= 32
	if rack(n, data, RN):
		S |= 64
	if S & 64 and quandle(n, data, RN):
		S |= 128
	return S
for _ in range(int(input())):
	n = int(input())
	data = [[int(x) for x in input().split(' ')] for _ in range(n)]
	print(solution(n, data))


def is_comm(mult_table):
	size = len(mult_table)
	for i in range(size):
		for j in range(i + 1, size):
			if mult_table[i][j] != mult_table[j][i]:
				return False
	return True

def is_ass(mult_table):
	size = len(mult_table)
	for i in range(size):
		for j in range(size):
			for k in range(size):
				if mult_table[i][mult_table[j][k]] != mult_table[mult_table[i][j]][k]:
					return False
	return True

def idempotent(mult_table):
	for j in range(len(mult_table)):
		if mult_table[j][j] != j:
			return False
	return True

def right_z(mult_table):
	for y in range(len(mult_table)):
		for row in mult_table:
			if row.count(y) != 1:
				return False
	return True

def left_w(mult_table):
	for y in range(len(mult_table)):
		for x in range(len(mult_table)):
			if [row[x] for row in mult_table].count(y) != 1:
				return False
	return True

def rack_relation(mult_table):
	size = len(mult_table)
	for i in range(size):
		for j in range(size):
			for k in range(size):
				if mult_table[i][mult_table[j][k]] != mult_table[mult_table[i][j]][mult_table[i][k]]:
					return False
	return True

def has_id(mult_table):
	size = len(mult_table)
	for i in range(size):
		for j in range(size):
			if mult_table[i][j] != j:
				break
			if mult_table[j][i] != j:
				break
		else:
			return True
	return False

def sig(mult_table):
	ans = 0
	has_right_z = right_z(mult_table)
	has_left_w = left_w(mult_table)
	is_quasi_group = has_right_z and has_left_w
	has_an_id = has_id(mult_table)
	comm = is_comm(mult_table)
	ass = is_ass(mult_table)
	if is_quasi_group:
		ans += 1
	if is_quasi_group and has_an_id:
		ans += 2
	if ass:
		ans += 4
		if has_an_id:
			ans += 8
			if is_quasi_group:
				ans += 16
				if comm:
					ans += 32
	if has_right_z and rack_relation(mult_table):
		ans += 64
		if idempotent(mult_table):
			ans += 128
	return ans
T = int(input())
for _ in range(T):
	n = int(input())
	mult_table = []
	for q in range(n):
		mult_table.append([int(x) for x in input().split()])
	print(sig(mult_table))


import math
import os
import random
import re
import sys

def isQuasigroup(M, MT, n):
	for i in range(n):
		if len(set(M[i])) != n:
			return False
	for i in range(n):
		if len(set(MT[i])) != n:
			return False
	return True

def hasUniqueUnit(M, MT, n):
	expectedRow = list(range(n))
	e = -1
	for i in range(n):
		if M[i] == expectedRow and MT[i] == expectedRow:
			if e == -1:
				e = i
			else:
				return (False, e)
	return (e != -1, e)

def isLoop(M, MT, n):
	if isQuasigroup(M, MT, n) == False:
		return False
	return hasUniqueUnit(M, MT, n)[0]

def isSemigroup(M, MT, n):
	for x in range(n):
		for z in range(n):
			xy_z = [MT[z][xy] for xy in M[x]]
			x_yz = [M[x][yz] for yz in MT[z]]
			if xy_z != x_yz:
				return False
	return True

def isMonoid(M, MT, n):
	if isSemigroup(M, MT, n) == False:
		return (False, -1)
	return hasUniqueUnit(M, MT, n)

def isGroup(M, MT, n):
	(isItMonoid, e) = isMonoid(M, MT, n)
	if isItMonoid == False:
		return False
	for i in range(n):
		if e in M[i]:
			j = M[i].index(e)
			if M[j][i] != e:
				return False
		else:
			return False
	return True

def isAbelianGroup(M, MT, n):
	if isGroup(M, MT, n) == False:
		return False
	for i in range(n):
		if M[i] != MT[i]:
			return False
	return True

def isRack(M, MT, n):
	for y in range(n):
		for z in range(n):
			x_yz = MT[M[y][z]]
			xy_xz = [M[MT[y][i]][MT[z][i]] for i in range(n)]
			if xy_xz != x_yz:
				return False
	for i in range(n):
		if len(set(M[i])) != n:
			return False
	return True

def isQuandle(M, MT, n):
	if isRack(M, MT, n) == False:
		return False
	if list(range(n)) != [M[x][x] for x in range(n)]:
		return False
	return True
T = int(input())
for t in range(T):
	M = []
	n = int(input())
	for i in range(n):
		charLine = input().split()
		line = [int(c) for c in charLine]
		assert len(line) == n
		M.append(line)
	MT = [[M[j][i] for j in range(n)] for i in range(n)]
	s = 0
	if isQuasigroup(M, MT, n) == True:
		s += 1
	if isLoop(M, MT, n) == True:
		s += 2
	if isSemigroup(M, MT, n) == True:
		s += 4
	if isMonoid(M, MT, n)[0] == True:
		s += 8
	if isGroup(M, MT, n) == True:
		s += 16
	if isAbelianGroup(M, MT, n) == True:
		s += 32
	if isRack(M, MT, n) == True:
		s += 64
	if isQuandle(M, MT, n) == True:
		s += 128
	print(s)


import os, sys, math, datetime
from collections import Counter
dbg = False
AEU = 0
A2EU = 1
EUA = 2
A1 = 3
A2 = 4
A3 = 5
EUAE = 6
A2S = 7
abelian_group = [(A2S, lambda op, x, y: op(x, y) == op(y, x))]
quandle = [(A1, lambda op, x: op(x, x) == x)]

class AlgebraicStructure:

	def __init__(self):
		self.X = None
		self.op = None

def set_any_diff(a, b):
	for x in a:
		if x not in b:
			return x
	return None

def get_generating_set(A):
	(op, X, XSet) = (A.op, A.X, set(A.X))
	(S, G, n) = (set(), set(), len(X))

	def powers(x):
		ret = set()
		p = x
		while True:
			ret.add(p)
			p = op(p, x)
			if p in ret:
				break
		return ret
	G.add(X[0])
	S |= powers(X[0])
	k = 1
	while k < 5 and len(S) != n:
		x = set_any_diff(XSet, S)
		T = powers(x)
		T2 = set()
		G.add(x)
		for t in T:
			for y in S:
				T2.add(op(y, t))
		S |= T
		S |= T2
		k += 1
	return G if len(S) == n else None

def get_identity(A):
	(op, X) = (A.op, A.X)
	for e in X:
		passed = True
		for x in X:
			if not (op(x, e) == x and op(e, x) == x):
				passed = False
				break
		if passed:
			return e
	return None

def has_unique_right_quotients(A):
	(op, X, n) = (A.op, A.X, len(A.X))
	range = set()
	for x in X:
		range.clear()
		for y in X:
			z = op(x, y)
			if z in range:
				return False
			range.add(z)
	return True

def has_unique_left_quotients(A):
	(op, X, n) = (A.op, A.X, len(A.X))
	range = set()
	for x in X:
		range.clear()
		for y in X:
			z = op(y, x)
			if z in range:
				return False
			range.add(z)
	return True

def is_group_with_specified_identify(A, e):
	(op, X) = (A.op, A.X)
	for x in X:
		exists = False
		for y in X:
			if op(x, y) == e and op(y, x) == e:
				exists = True
				break
		if not exists:
			return False
	return True

def is_associative(A):
	X = A.X
	op = A.op
	for a in X:
		for x in X:
			xa = op(x, a)
			for y in X:
				if op(x, op(a, y)) != op(xa, y):
					return False
	return True

def is_rack(A):
	X = A.X
	op = A.op
	for x in X:
		for y in X:
			xy = op(x, y)
			for z in X:
				if op(x, op(y, z)) != op(xy, op(x, z)):
					return False
	return True

def test_all_3_exists_unique(A, f):
	(op, X) = (A.op, A.X)
	for x in X:
		for y in X:
			c = 0
			for z in X:
				if f(op, x, y, z):
					c += 1
					if c >= 2:
						return False
			if c == 0:
				return False
	return True

def test_exists_unique_all(A, f):
	(op, X) = (A.op, A.X)
	c = 0
	for x in X:
		passed = True
		for y in X:
			if not f(op, x, y):
				passed = False
				break
		if passed:
			c += 1
			if c >= 2:
				return False
	return c == 1

def test_exists_unique_all_exists(A, f):
	(fExistsUnique, fAllExists) = f
	(op, X) = (A.op, A.X)
	c = 0
	e = None
	for x in X:
		passed = True
		for y in X:
			if not fExistsUnique(op, x, y):
				passed = False
				break
		if passed:
			e = x
			c += 1
			if c >= 2:
				return False
	if e is None:
		return False
	for x in X:
		passed = False
		for y in X:
			if fAllExists(op, e, x, y):
				passed = True
				break
		if not passed:
			return False
	return True

def test_all_1(A, f):
	(op, X) = (A.op, A.X)
	for x in X:
		if not f(op, x):
			return False
	return True

def test_all_2(A, f):
	(op, X) = (A.op, A.X)
	for x in X:
		for y in X:
			if not f(op, x, y):
				return False
	return True

def test_all_2_symmetric(A, f):
	(op, X) = (A.op, A.X)
	for (i, x) in enumerate(X):
		for y in X[i:]:
			if not f(op, x, y):
				return False
	return True

def test_all_3(A, f):
	(op, X) = (A.op, A.X)
	for x in X:
		for y in X:
			for z in X:
				if not f(op, x, y, z):
					return False
	return True

def test_condition1(A, cond, descr=None):
	for (c, f) in cond:
		if c == A2EU:
			if not test_all_3_exists_unique(A, f):
				return False
		elif c == EUA:
			if not test_exists_unique_all(A, f):
				return False
		elif c == A1:
			if not test_all_1(A, f):
				return False
		elif c == A2:
			if not test_all_2(A, f):
				return False
		elif c == A2S:
			if not test_all_2_symmetric(A, f):
				return False
		elif c == A3:
			if not test_all_3(A, f):
				return False
		elif c == EUAE:
			if not test_exists_unique_all_exists(A, f):
				return False
		else:
			raise ValueError(c)
	return True

def test_condition(A, cond, descr=None):
	t1 = datetime.datetime.utcnow()
	ret = test_condition1(A, cond)
	t2 = datetime.datetime.utcnow()
	if (t2 - t1).total_seconds() >= 0.1:
		if dbg:
			print('{} {}'.format(t2 - t1, descr), file=sys.stderr)
	return ret

def algebra_magic(A):
	what = []
	(e, echecked) = (None, False)
	hasURQ = has_unique_right_quotients(A)
	S = 0
	if hasURQ and has_unique_left_quotients(A):
		what.append('quasigroup')
		S += 1
		e = get_identity(A)
		echecked = True
	if S & 1 != 0 and e is not None:
		what.append('loop')
		S += 2
	if is_associative(A):
		what.append('semigroup')
		S += 4
		if not echecked:
			e = get_identity(A)
			echecked = True
	if S & 4 != 0 and e is not None:
		what.append('monoid')
		S += 8
	if S & 8 != 0 and S & 1 != 0 and is_group_with_specified_identify(A, e):
		what.append('group')
		S += 16
	if S & 16 != 0 and test_condition(A, abelian_group, 'abelian'):
		what.append('abelian')
		S += 32
	if hasURQ and is_rack(A):
		what.append('rack')
		S += 64
	if S & 64 != 0 and test_condition(A, quandle, 'quandle'):
		what.append('quandle')
		S += 128
	if dbg:
		print(' '.join(what), file=sys.stderr)
	return S

def solve(n, vals):
	A = AlgebraicStructure()
	A.X = list(range(n))
	A.op = lambda x, y: vals[x][y]
	return algebra_magic(A)

def main():
	lines = sys.stdin.read().splitlines()
	t = int(lines[0])
	i = 1
	for _ in range(t):
		n = int(lines[i])
		i += 1
		op = []
		for _ in range(n):
			vals = list(map(int, lines[i].split()))
			i += 1
			op.append(vals)
		print(solve(n, op))
main()


import sys
import os

def lire_colonne(arr, num):
	colonne = [arr[i][num] for i in range(len(arr))]
	return colonne

def lire_ligne(arr, num):
	return arr[num]

def ordonne(liste):
	test = [True] * len(liste)
	for elt in liste:
		if elt >= len(liste):
			return False
		test[elt] = False
	if test.count(True) > 0:
		return False
	else:
		return True

def indice(liste, val):
	resul = []
	for (i, elt) in enumerate(liste):
		if elt == val:
			resul.append(i)
	return resul

def compare(liste, patron):
	for i in range(len(liste)):
		if liste[i] != patron[i]:
			return False
	return True

def neutre(arr, n):
	candidats_e = indice(lire_ligne(arr, 0), 0)
	for e in candidats_e:
		if compare(lire_ligne(arr, e), list(range(n))):
			if compare(lire_colonne(arr, e), list(range(n))):
				return (True, e)
	return (False, None)

def EstQuasigroup(arr, n):
	for x in range(n):
		if not ordonne(lire_ligne(arr, x)):
			return False
		if not ordonne(lire_colonne(arr, x)):
			return False
	return True

def EstSemigroup(arr, n):
	for x in range(n):
		for y in range(n):
			for z in range(n):
				gauche = arr[arr[x][y]][z]
				droite = arr[x][arr[y][z]]
				if gauche != droite:
					return False
	return True

def inverse(arr, n, e):
	for x in range(n):
		candidats_y = indice(lire_ligne(arr, x), e)
		ok = False
		for y in candidats_y:
			if arr[y][x] == e:
				ok = True
				break
		if not ok:
			return False
	return True

def symetrie(arr, n):
	for x in range(n):
		for y in range(n):
			if arr[x][y] != arr[y][x]:
				return False
	return True

def EstRack(arr, n):
	for x in range(n):
		for y in range(n):
			candidats_z = indice(lire_ligne(arr, x), y)
			if len(candidats_z) != 1:
				return False
			for z in range(n):
				if arr[x][arr[y][z]] != arr[arr[x][y]][arr[x][z]]:
					return False
	return True

def reflexive(arr, n):
	for x in range(n):
		if arr[x][x] != x:
			return False
	return True

def identifier(arr, n):
	S = 0
	e = None
	if EstQuasigroup(arr, n):
		S += 1
		(EstNeutre, e) = neutre(arr, n)
		if EstNeutre:
			S += 2
	if EstSemigroup(arr, n):
		S += 4
		Monoid = False
		if S >= 7:
			S += 8
			Monoid = True
		elif S == 4:
			(EstNeutre, e) = neutre(arr, n)
			if EstNeutre:
				S += 8
			Monoid = True
		if Monoid:
			if inverse(arr, n, e):
				S += 16
				if symetrie(arr, n):
					S += 32
	if EstRack(arr, n):
		S += 64
		if reflexive(arr, n):
			S += 128
	return S
t = int(input())
for t_itr in range(t):
	n = int(input())
	M = list(range(n))
	arr = []
	for n_itr in range(n):
		arr.append(list(map(int, input().split())))
	print(identifier(arr, n))


import sys

def classify(optab):
	mrank = len(optab)
	mrange = range(mrank)
	is_magma = all((len(row) == mrank for row in optab)) and all((optab[x][y] in mrange for x in mrange for y in mrange))
	if not is_magma:
		return -1
	result = 0
	identity = None
	for e in mrange:
		is_ident = True
		for x in mrange:
			if optab[e][x] != x or optab[x][e] != x:
				is_ident = False
				break
		if is_ident:
			identity = e
	has_inverse = None
	if identity is not None:
		has_inverse = all((any((optab[x][y] == optab[y][x] == identity for y in mrange)) for x in mrange))
	is_commutative = all((optab[i][j] == optab[j][i] for i in mrange for j in range(i)))
	is_associative = all((optab[i][optab[j][k]] == optab[optab[i][j]][k] for i in mrange for j in mrange for k in mrange))
	is_quasi = True
	for i in mrange:
		row_set = col_set = 0
		for j in mrange:
			row_set |= 1 << optab[i][j]
			col_set |= 1 << optab[j][i]
		if not row_set == col_set == (1 << mrank) - 1:
			is_quasi = False
			break
	if is_quasi:
		result += 1
	is_loop = is_quasi and identity is not None
	if is_loop:
		result += 2
	is_semigroup = is_associative
	if is_semigroup:
		result += 4
	is_monoid = is_semigroup and identity is not None
	if is_monoid:
		result += 8
	is_group = is_monoid and has_inverse
	if is_group:
		result += 16
	is_abelian_group = is_group and is_commutative
	if is_abelian_group:
		result += 32
	is_rack = False
	if all((optab[x][optab[y][z]] == optab[optab[x][y]][optab[x][z]] for x in mrange for y in mrange for z in mrange)):
		is_rack = True
		for x in mrange:
			row_set = 0
			for y in mrange:
				row_set |= 1 << optab[x][y]
			if row_set != (1 << mrank) - 1:
				is_rack = False
				break
	if is_rack:
		result += 64
	is_quandle = is_rack and all((optab[x][x] == x for x in mrange))
	if is_quandle:
		result += 128
	return result
T = int(input())
for t in range(T):
	n = int(input())
	optab = [[int(s) for s in input().split()] for _ in range(n)]
	result = classify(optab)
	print(result)


for _ in range(int(input())):
	arr = []
	n = int(input())
	for _ in range(n):
		arr.append(list(map(int, input().split())))
	qg1 = True
	qg2 = True
	for i in range(n):
		arr2 = list(range(n))
		arr3 = list(range(n))
		for j in range(n):
			if arr[i][j] in arr2:
				arr2.remove(arr[i][j])
			else:
				qg1 = False
			if arr[j][i] in arr3:
				arr3.remove(arr[j][i])
			else:
				qg2 = False
			if not qg1 and (not qg2):
				break
		if not qg1 and (not qg2):
			break
	loop = False
	qg = qg1 and qg2
	e = -1
	for i in range(n):
		works = True
		for j in range(n):
			if arr[i][j] != arr[j][i] or arr[i][j] != j:
				works = False
				break
		if works and e == -1:
			loop = True
			e = i
		elif works:
			loop = False
	sg = True
	rack = True
	for i in range(n):
		for j in range(n):
			for k in range(n):
				if arr[arr[i][j]][k] != arr[i][arr[j][k]]:
					sg = False
				if arr[i][arr[j][k]] != arr[arr[i][j]][arr[i][k]]:
					rack = False
				if not sg and (not rack):
					break
			if not sg and (not rack):
				break
		if not sg:
			break
	rack = rack and qg1
	mon = sg and loop
	group = qg and mon
	ab = False
	if group:
		ab = True
		for i in range(n):
			for j in range(i + 1, n):
				if arr[i][j] != arr[j][i]:
					ab = False
					break
			if not ab:
				break
	qdl = False
	if rack:
		qdl = True
		for i in range(n):
			if arr[i][i] != i:
				qdl = False
				break
	loop = loop and qg
	s = 1 * qg + 2 * loop + 4 * sg + 8 * mon + 16 * group + 32 * ab + 64 * rack + 128 * qdl
	print(s)


def isQuasiGroup(table):
	size = len(table)
	for i in range(size):
		rowValues = set()
		columnValues = set()
		for j in range(size):
			rowValues.add(table[i][j])
			columnValues.add(table[j][i])
		if len(rowValues) != size or len(columnValues) != size:
			return False
	return True

def isLeftIdentity(x, table):
	size = len(table)
	return all((table[x][i] == i for i in range(size)))

def isRightIdentity(x, table):
	size = len(table)
	return all((table[i][x] == i for i in range(size)))

def isQuasiGroupALoop(table):
	size = len(table)
	hasLeftIdentity = False
	hasRightIdentity = False
	for x in range(size):
		if not hasLeftIdentity and isLeftIdentity(x, table):
			hasLeftIdentity = True
		if not hasRightIdentity and isRightIdentity(x, table):
			hasRightIdentity = True
	return hasLeftIdentity and hasRightIdentity

def isSemiGroup(table):
	size = len(table)
	for x in range(size):
		for y in range(size):
			for z in range(size):
				if table[table[x][y]][z] != table[x][table[y][z]]:
					return False
	return True

def getUniqueIdentity(table):
	size = len(table)
	rightIdentity = None
	for x in range(size):
		if isRightIdentity(x, table):
			if rightIdentity is not None:
				return None
			rightIdentity = x
	leftIdentity = None
	for x in range(size):
		if isLeftIdentity(x, table):
			if leftIdentity is not None:
				return None
			leftIdentity = x
	return rightIdentity if rightIdentity == leftIdentity else None

def isMonoidAGroup(e, table):
	size = len(table)
	for x in range(size):
		hasLeftInverse = False
		hasRightInverse = False
		for y in range(size):
			if table[y][x] == e:
				hasLeftInverse = True
			if table[x][y] == e:
				hasRightInverse = True
			if hasLeftInverse and hasRightInverse:
				break
		if not (hasLeftInverse and hasRightInverse):
			return False
	return True

def isCommutative(table):
	size = len(table)
	for x in range(size):
		for y in range(size):
			if table[x][y] != table[y][x]:
				return False
	return True

def isRack(table):
	size = len(table)
	for x in range(size):
		for y in range(size):
			for z in range(size):
				if table[x][table[y][z]] != table[table[x][y]][table[x][z]]:
					return False
	for x in range(size):
		for y in range(size):
			hasZ = False
			for z in range(size):
				if table[x][z] == y:
					if hasZ:
						return False
					else:
						hasZ = True
			if not hasZ:
				return False
	return True

def isRackAQuandle(table):
	size = len(table)
	for x in range(size):
		if table[x][x] != x:
			return False
	return True

def getMagicNumber(table):
	S = 0
	if isQuasiGroup(table):
		S += 1
		if isQuasiGroupALoop(table):
			S += 2
	if isSemiGroup(table):
		S += 4
		e = getUniqueIdentity(table)
		if e is not None:
			S += 8
			if isMonoidAGroup(e, table):
				S += 16
				if isCommutative(table):
					S += 32
	if isRack(table):
		S += 64
		if isRackAQuandle(table):
			S += 128
	return S
T = int(input())
for t in range(T):
	size = int(input())
	table = []
	for _ in range(size):
		table.append([int(s) for s in input().split()])
	print(getMagicNumber(table))


class Magma(object):

	def __init__(self, size, *table):
		self.size = size
		self.table = list(table)
		columns = [[0 for _ in range(size)] for _ in range(size)]
		for i in range(size):
			for j in range(size):
				columns[j][i] = table[i][j]
		self.columns = columns
		self.quasigroup = False
		self.loop = False
		self.semigroup = False
		self.monoid = False
		self.group = False
		self.abelian = False
		self.rack = False
		self.quandle = False
		self.magic = 0

	def isQuasigroup(self):
		for x in range(self.size):
			checkh = [False for _ in range(self.size)]
			checkv = [False for _ in range(self.size)]
			for w in range(self.size):
				if not checkh[self.table[x][w]]:
					checkh[self.table[x][w]] = True
				else:
					return
				if not checkv[self.table[w][x]]:
					checkv[self.table[w][x]] = True
				else:
					return
		self.quasigroup = True
		self.magic += 1
		return

	def isLoop(self):
		if not self.quasigroup:
			return
		check = [i for i in range(self.size)]
		for e in range(self.size):
			if self.table[e] == check:
				possibleE = e
				break
		else:
			return
		if self.columns[possibleE] == check:
			self.loop = True
			self.magic += 2
		return

	def isSemigroup(self):
		for x in range(self.size):
			for y in range(self.size):
				for z in range(self.size):
					if self.table[self.table[x][y]][z] != self.table[x][self.table[y][z]]:
						return
		self.semigroup = True
		self.magic += 4
		return

	def isMonoid(self):
		if not self.semigroup:
			return
		if self.loop:
			self.monoid = True
			self.magic += 8
			return
		possibleEs = []
		check = [i for i in range(self.size)]
		for e in range(self.size):
			if self.table[e] == check:
				possibleEs.append(e)
		if possibleEs == []:
			return
		for e in possibleEs:
			if self.columns[e] == check:
				self.monoid = True
				self.magic += 8
				return
		return

	def isGroup(self):
		if not self.loop or not self.semigroup:
			return
		self.group = True
		self.magic += 16
		return

	def isAbelian(self):
		if self.group and self.table == self.columns:
			self.abelian = True
			self.magic += 32
			return
		return

	def isRack(self):
		if self.group and self.size > 1:
			return
		for x in range(self.size):
			checkh = [False for _ in range(self.size)]
			for w in range(self.size):
				if not checkh[self.table[x][w]]:
					checkh[self.table[x][w]] = True
				else:
					return
			for y in range(self.size):
				for z in range(self.size):
					if self.table[x][self.table[y][z]] != self.table[self.table[x][y]][self.table[x][z]]:
						return
		self.rack = True
		self.magic += 64
		return

	def isQuandle(self):
		if not self.rack:
			return
		for x in range(self.size):
			if self.table[x][x] != x:
				return
		self.quandle = True
		self.magic += 128
		return
T = int(input())
for t in range(T):
	n = int(input())
	rows = []
	for i in range(n):
		row = input()
		row = row.split()
		rows.append(list(map(int, row)))
	M = Magma(n, *rows)
	M.isQuasigroup()
	M.isLoop()
	M.isSemigroup()
	M.isMonoid()
	M.isGroup()
	M.isAbelian()
	M.isRack()
	M.isQuandle()
	print(M.magic)


from collections import defaultdict
from itertools import product
from functools import reduce
from operator import and_

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		cayley = []
		for n in range(N):
			cayley.append(list(map(int, input().split())))
		print(solve(cayley))

def solve(table):
	magic = 0
	n = len(table)
	M = list(range(n))
	op = {}
	lset = defaultdict(set)
	rset = defaultdict(set)
	for (i, row) in enumerate(table):
		for (j, k) in enumerate(row):
			op[i, j] = k
			lset[j, k].add(i)
			rset[i, k].add(j)
	if all((len(lset[xz]) == 1 and len(rset[xz]) == 1 for xz in product(M, repeat=2))):
		magic += 1 << 0
		e = list(lset[0, 0])[0]
		if all((e in lset[x, x] and e in rset[x, x] for x in M)):
			magic += 1 << 1
	if all((op[op[x, y], z] == op[x, op[y, z]] for (x, y, z) in product(M, repeat=3))):
		magic += 1 << 2
		e_set = reduce(and_, (lset[x, x] for x in M))
		e_set &= reduce(and_, (rset[x, x] for x in M))
		if len(e_set) == 1:
			magic += 1 << 3
			e = list(e_set)[0]
			if all((len(lset[x, e]) == 1 and lset[x, e] == rset[x, e] for x in M)):
				magic += 1 << 4
				if all((op[x, y] == op[y, x] for x in M for y in M)):
					magic += 1 << 5
	if all((len(rset[xy]) == 1 for xy in product(M, repeat=2))):
		if all((op[x, op[y, z]] == op[op[x, y], op[x, z]] for (x, y, z) in product(M, repeat=3))):
			magic += 1 << 6
			if all((op[x, x] == x for x in M)):
				magic += 1 << 7
	return magic
main()


def isDivisible(M):
	N = len(M)
	return min((len({M[x][z] for z in range(N)}) for x in range(N))) == N == min((len({M[z][x] for z in range(N)}) for x in range(N)))

def getIdentity(M):
	for e in range(len(M)):
		for x in range(len(M)):
			if M[e][x] == x == M[x][e]:
				continue
			else:
				break
		else:
			return e
	return None

def isAssociative(M):
	N = len(M)
	for a in range(N):
		for b in range(N):
			for c in range(N):
				if M[a][M[b][c]] != M[M[a][b]][c]:
					return False
	return True

def invertsTo(M, e):
	N = len(M)
	for x in range(N):
		for y in range(N):
			if M[x][y] == M[y][x] == e:
				break
		else:
			return False
	return True

def isCommutative(M):
	for i in range(len(M)):
		for j in range(i + 1, len(M)):
			if M[i][j] != M[j][i]:
				return False
	return True

def autoInversion(M):
	for x in range(len(M)):
		if M[x][x] != x:
			return False
	return True

def isRack(M):
	N = len(M)
	left = min((len({M[x][z] for z in range(N)}) for x in range(N))) == N
	if not left:
		return False
	for a in range(N):
		for b in range(N):
			for c in range(N):
				if M[a][M[b][c]] != M[M[a][b]][M[a][c]]:
					return False
	return True
M = [[0, 0, 0, 0, 0], [2, 1, 1, 1, 1], [1, 2, 2, 2, 2], [4, 4, 4, 3, 3], [3, 3, 3, 4, 4]]
M = [[1, 3, 2, 5, 4], [1, 2, 3, 5, 4], [1, 2, 3, 5, 4], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]]

def magicNumber(M):
	divides = isDivisible(M)
	identity = getIdentity(M)
	has_identity = identity != None
	inverts = has_identity and invertsTo(M, identity)
	associates = isAssociative(M)
	auto_inverts = autoInversion(M)
	commutes = isCommutative(M)
	quasigroup = divides
	loop = divides and has_identity
	semigroup = associates
	monoid = associates and has_identity
	group = divides and associates and inverts and has_identity
	abelian_group = group and commutes
	rack = isRack(M)
	quandle = rack and auto_inverts
	number = [quasigroup, loop, semigroup, monoid, group, abelian_group, rack, quandle]
	n = 0
	while number:
		n = 2 * n + number.pop()
	return n
num_cases = int(input())
for case in range(num_cases):
	N = int(input())
	M = [list(map(int, input().split())) for i in range(N)]
	print(magicNumber(M))


def isDivisible(M):
	N = len(M)
	return min((len({M[x][z] for z in range(N)}) for x in range(N))) == N == min((len({M[z][x] for z in range(N)}) for x in range(N)))

def getIdentity(M):
	for e in range(len(M)):
		for x in range(len(M)):
			if M[e][x] == x == M[x][e]:
				continue
			else:
				break
		else:
			return e
	return None

def isAssociative(M):
	N = len(M)
	for a in range(N):
		for b in range(N):
			for c in range(N):
				if M[a][M[b][c]] != M[M[a][b]][c]:
					return False
	return True

def invertsTo(M, e):
	N = len(M)
	for x in range(N):
		for y in range(N):
			if M[x][y] == M[y][x] == e:
				break
		else:
			return False
	return True

def isCommutative(M):
	for i in range(len(M)):
		for j in range(i + 1, len(M)):
			if M[i][j] != M[j][i]:
				return False
	return True

def autoInversion(M):
	for x in range(len(M)):
		if M[x][x] != x:
			return False
	return True

def isRack(M):
	N = len(M)
	left = min((len({M[x][z] for z in range(N)}) for x in range(N))) == N
	if not left:
		return False
	for a in range(N):
		for b in range(N):
			for c in range(N):
				if M[a][M[b][c]] != M[M[a][b]][M[a][c]]:
					return False
	return True
M = [[0, 0, 0, 0, 0], [2, 1, 1, 1, 1], [1, 2, 2, 2, 2], [4, 4, 4, 3, 3], [3, 3, 3, 4, 4]]
M = [[1, 3, 2, 5, 4], [1, 2, 3, 5, 4], [1, 2, 3, 5, 4], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]]

def magicNumber(M):
	divides = isDivisible(M)
	identity = getIdentity(M)
	has_identity = identity != None
	inverts = has_identity and invertsTo(M, identity)
	associates = isAssociative(M)
	auto_inverts = autoInversion(M)
	commutes = isCommutative(M)
	quasigroup = divides
	loop = divides and has_identity
	semigroup = associates
	monoid = associates and has_identity
	group = divides and associates and inverts and has_identity
	abelian_group = group and commutes
	rack = isRack(M)
	quandle = rack and auto_inverts
	number = [quasigroup, loop, semigroup, monoid, group, abelian_group, rack, quandle]
	n = 0
	while number:
		n = 2 * n + number.pop()
	return n
num_cases = int(input())
for case in range(num_cases):
	N = int(input())
	M = [list(map(int, input().split())) for i in range(N)]
	print(magicNumber(M))


def isDivisible(M):
	N = len(M)
	return min((len({M[x][z] for z in range(N)}) for x in range(N))) == N == min((len({M[z][x] for z in range(N)}) for x in range(N)))

def getIdentity(M):
	for e in range(len(M)):
		for x in range(len(M)):
			if M[e][x] == x == M[x][e]:
				continue
			else:
				break
		else:
			return e
	return None

def isAssociative(M):
	N = len(M)
	for a in range(N):
		for b in range(N):
			for c in range(N):
				if M[a][M[b][c]] != M[M[a][b]][c]:
					return False
	return True

def invertsTo(M, e):
	N = len(M)
	for x in range(N):
		for y in range(N):
			if M[x][y] == M[y][x] == e:
				break
		else:
			return False
	return True

def isCommutative(M):
	for i in range(len(M)):
		for j in range(i + 1, len(M)):
			if M[i][j] != M[j][i]:
				return False
	return True

def autoInversion(M):
	for x in range(len(M)):
		if M[x][x] != x:
			return False
	return True

def isRack(M):
	N = len(M)
	left = min((len({M[x][z] for z in range(N)}) for x in range(N))) == N
	if not left:
		return False
	for a in range(N):
		for b in range(N):
			for c in range(N):
				if M[a][M[b][c]] != M[M[a][b]][M[a][c]]:
					return False
	return True
M = [[0, 0, 0, 0, 0], [2, 1, 1, 1, 1], [1, 2, 2, 2, 2], [4, 4, 4, 3, 3], [3, 3, 3, 4, 4]]
M = [[1, 3, 2, 5, 4], [1, 2, 3, 5, 4], [1, 2, 3, 5, 4], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]]

def magicNumber(M):
	divides = isDivisible(M)
	identity = getIdentity(M)
	has_identity = identity != None
	inverts = has_identity and invertsTo(M, identity)
	associates = isAssociative(M)
	auto_inverts = autoInversion(M)
	commutes = isCommutative(M)
	quasigroup = divides
	loop = divides and has_identity
	semigroup = associates
	monoid = associates and has_identity
	group = divides and associates and inverts and has_identity
	abelian_group = group and commutes
	rack = isRack(M)
	quandle = rack and auto_inverts
	number = [quasigroup, loop, semigroup, monoid, group, abelian_group, rack, quandle]
	n = 0
	while number:
		n = 2 * n + number.pop()
	return n
num_cases = int(input())
for case in range(num_cases):
	N = int(input())
	M = [list(map(int, input().split())) for i in range(N)]
	print(magicNumber(M))


def isDivisible(M):
	N = len(M)
	return min((len({M[x][z] for z in range(N)}) for x in range(N))) == N == min((len({M[z][x] for z in range(N)}) for x in range(N)))

def getIdentity(M):
	for e in range(len(M)):
		for x in range(len(M)):
			if M[e][x] == x == M[x][e]:
				continue
			else:
				break
		else:
			return e
	return None

def isAssociative(M):
	N = len(M)
	for a in range(N):
		for b in range(N):
			for c in range(N):
				if M[a][M[b][c]] != M[M[a][b]][c]:
					return False
	return True

def invertsTo(M, e):
	N = len(M)
	for x in range(N):
		for y in range(N):
			if M[x][y] == M[y][x] == e:
				break
		else:
			return False
	return True

def isCommutative(M):
	for i in range(len(M)):
		for j in range(i + 1, len(M)):
			if M[i][j] != M[j][i]:
				return False
	return True

def autoInversion(M):
	for x in range(len(M)):
		if M[x][x] != x:
			return False
	return True

def isRack(M):
	N = len(M)
	left = min((len({M[x][z] for z in range(N)}) for x in range(N))) == N
	if not left:
		return False
	for a in range(N):
		for b in range(N):
			for c in range(N):
				if M[a][M[b][c]] != M[M[a][b]][M[a][c]]:
					return False
	return True
M = [[0, 0, 0, 0, 0], [2, 1, 1, 1, 1], [1, 2, 2, 2, 2], [4, 4, 4, 3, 3], [3, 3, 3, 4, 4]]
M = [[1, 3, 2, 5, 4], [1, 2, 3, 5, 4], [1, 2, 3, 5, 4], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]]

def magicNumber(M):
	divides = isDivisible(M)
	identity = getIdentity(M)
	has_identity = identity != None
	inverts = has_identity and invertsTo(M, identity)
	associates = isAssociative(M)
	auto_inverts = autoInversion(M)
	commutes = isCommutative(M)
	quasigroup = divides
	loop = divides and has_identity
	semigroup = associates
	monoid = associates and has_identity
	group = divides and associates and inverts and has_identity
	abelian_group = group and commutes
	rack = isRack(M)
	quandle = rack and auto_inverts
	number = [quasigroup, loop, semigroup, monoid, group, abelian_group, rack, quandle]
	n = 0
	while number:
		n = 2 * n + number.pop()
	return n
num_cases = int(input())
for case in range(num_cases):
	N = int(input())
	M = [list(map(int, input().split())) for i in range(N)]
	print(magicNumber(M))


def isDivisible(M):
	N = len(M)
	return min((len({M[x][z] for z in range(N)}) for x in range(N))) == N == min((len({M[z][x] for z in range(N)}) for x in range(N)))

def getIdentity(M):
	for e in range(len(M)):
		for x in range(len(M)):
			if M[e][x] == x == M[x][e]:
				continue
			else:
				break
		else:
			return e
	return None

def isAssociative(M):
	N = len(M)
	for a in range(N):
		for b in range(N):
			for c in range(N):
				if M[a][M[b][c]] != M[M[a][b]][c]:
					return False
	return True

def invertsTo(M, e):
	N = len(M)
	for x in range(N):
		for y in range(N):
			if M[x][y] == M[y][x] == e:
				break
		else:
			return False
	return True

def isCommutative(M):
	for i in range(len(M)):
		for j in range(i + 1, len(M)):
			if M[i][j] != M[j][i]:
				return False
	return True

def autoInversion(M):
	for x in range(len(M)):
		if M[x][x] != x:
			return False
	return True

def isRack(M):
	N = len(M)
	left = min((len({M[x][z] for z in range(N)}) for x in range(N))) == N
	if not left:
		return False
	for a in range(N):
		for b in range(N):
			for c in range(N):
				if M[a][M[b][c]] != M[M[a][b]][M[a][c]]:
					return False
	return True
M = [[0, 0, 0, 0, 0], [2, 1, 1, 1, 1], [1, 2, 2, 2, 2], [4, 4, 4, 3, 3], [3, 3, 3, 4, 4]]
M = [[1, 3, 2, 5, 4], [1, 2, 3, 5, 4], [1, 2, 3, 5, 4], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]]

def magicNumber(M):
	divides = isDivisible(M)
	identity = getIdentity(M)
	has_identity = identity != None
	inverts = has_identity and invertsTo(M, identity)
	associates = isAssociative(M)
	auto_inverts = autoInversion(M)
	commutes = isCommutative(M)
	quasigroup = divides
	loop = divides and has_identity
	semigroup = associates
	monoid = associates and has_identity
	group = divides and associates and inverts and has_identity
	abelian_group = group and commutes
	rack = isRack(M)
	quandle = rack and auto_inverts
	number = [quasigroup, loop, semigroup, monoid, group, abelian_group, rack, quandle]
	n = 0
	while number:
		n = 2 * n + number.pop()
	return n
num_cases = int(input())
for case in range(num_cases):
	N = int(input())
	M = [list(map(int, input().split())) for i in range(N)]
	print(magicNumber(M))