David has several containers, each with a number of balls in it.  He has just enough containers to sort each type of ball he has into its own container.  David wants to sort the balls using his sort method.

David wants to perform some number of swap operations such that:

Each container contains only balls of the same type.
No two balls of the same type are located in different containers.

Example   

$containers=[[1,4],[2,3]]$   

David has $n=2$ containers and $2$ different types of balls, both of which are numbered from $\mbox{0}$ to $n-1=1$. The distribution of ball types per container are shown in the following diagram.   

In a single operation, David can swap two balls located in different containers.

The diagram below depicts a single swap operation:

In this case, there is no way to have all green balls in one container and all red in the other using only swap operations.  Return Impossible.  

You must perform $\textit{q}$ queries where each query is in the form of a matrix, $\mbox{M}$. For each query, print Possible on a new line if David can satisfy the conditions above for the given matrix.  Otherwise, print Impossible.  

Function Description  

Complete the organizingContainers function in the editor below.   

organizingContainers has the following parameter(s):  

int containter[n][m]: a two dimensional array of integers that represent the number of balls of each color in each container  

Returns   

string:  either Possible or Impossible     

Input Format

The first line contains an integer $\textit{q}$, the number of queries.  

Each of the next $\textit{q}$ sets of lines is as follows:  

The first line contains an integer $n$, the number of containers (rows) and ball types (columns).        
Each of the next $n$ lines contains $n$ space-separated integers describing row $containers[i]$.

Constraints

$1\leq q\leq10$  
$1\leq n\leq100$  
$0\leq\textit{containers}[i][j]\leq10^9$

Scoring

For $33\%$ of score, $1\leq n\leq10$.  
For $\textbf{100\%}$ of score, $1\leq n\leq100$.

Output Format

For each query, print Possible on a new line if David can satisfy the conditions above for the given matrix.  Otherwise, print Impossible.

Sample Input 0
2
2
1 1
1 1
2
0 2
1 1

Sample Output 0
Possible
Impossible

Explanation 0

We perform the following $q=2$ queries:

The diagram below depicts one possible way to satisfy David's requirements for the first query:
 
Thus, we print Possible on a new line.
The diagram below depicts the matrix for the second query:
 
No matter how many times we swap balls of type $\boldsymbol{t_0}$ and $\boldsymbol{t_1}$ between the two containers, we'll never end up with one container only containing type $\boldsymbol{t_0}$ and the other container only containing type $\boldsymbol{t_1}$. Thus, we print Impossible on a new line.

Sample Input 1
2
3
1 3 1
2 1 2
3 3 3
3
0 2 1
1 1 1
2 0 0

Sample Output 1
Impossible
Possible

Source: hackerrank | Difficulty: MEDIUM
Tags: Implementation


Solutions:
import sys
from collections import Counter
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	rows = Counter()
	cols = Counter()
	for i in range(n):
		rows[sum(M[i])] += 1
		tmp = 0
		for row in M:
			tmp += row[i]
		cols[tmp] += 1
	print('Possible' if rows == cols else 'Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	count_containers = [sum(M[i]) for i in range(n)]
	M_trans = list(zip(*M))
	count_types = [sum(M_trans[i]) for i in range(n)]
	if sorted(count_containers) == sorted(count_types):
		print('Possible')
	else:
		print('Impossible')


import sys
from collections import Counter
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	containers = []
	balls = [0] * n
	for row in range(n):
		containers.append(sum(M[row]))
		for col in range(n):
			balls[col] += M[row][col]
	containers.sort()
	balls.sort()
	if containers == balls:
		print('Possible')
	else:
		print('Impossible')


for _ in range(int(input())):
	n = int(input())
	M = []
	for M_i in range(n):
		M_t = [int(a) for a in input().split()]
		M.append(M_t)
	Mt = [list(a) for a in zip(*M)]
	rows = [sum(a) for a in M]
	cols = [sum(a) for a in Mt]
	if sorted(rows) == sorted(cols):
		print('Possible')
	else:
		print('Impossible')


def main():
	for _ in range(int(input())):
		n = int(input())
		ball_counts = [0] * n
		container_counts = [0] * n
		for row in range(n):
			for (i, c) in enumerate(map(int, input().split())):
				ball_counts[i] += c
				container_counts[row] += c
		print('Possible' if sorted(ball_counts) == sorted(container_counts) else 'Impossible')
main()


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	l1 = []
	for mi in M:
		l1.append(sum(mi))
	l2 = []
	for mi in range(0, n):
		s = 0
		for i in range(0, n):
			s += M[i][mi]
		l2.append(s)
	if sorted(l1) == sorted(l2):
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	M2 = [[] for i in range(n)]
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
		for j in range(n):
			M2[j].append(M_t[j])
	a1 = [sum(m1) for m1 in M]
	a2 = [sum(m2) for m2 in M2]
	a1.sort()
	a2.sort()
	if a1 == a2:
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	balls = [0] * n
	for i in range(n):
		for j in range(n):
			balls[j] += M[i][j]
	sizes = [0] * n
	for i in range(n):
		sizes[i] = sum(M[i])
	sizes.sort()
	balls.sort()
	if sizes == balls:
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	typeCounts = [0 for i in range(n)]
	types = dict()
	containerSizes = [0 for i in range(n)]
	for c in range(n):
		for t in range(n):
			typeCounts[t] += M[c][t]
			containerSizes[c] += M[c][t]
	for typeCount in typeCounts:
		if typeCount in types:
			types[typeCount] += 1
		else:
			types[typeCount] = 1
	possible = True
	for containerSize in containerSizes:
		if not containerSize in types:
			possible = False
			break
		if types[containerSize] < 1:
			possible = False
			break
		types[containerSize] -= 1
	if possible:
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	capacity_h = []
	capacity_w = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
		capacity_h.append(sum(M_t))
	for i in range(n):
		capacity_w.append(0)
		for j in range(n):
			capacity_w[i] += M[j][i]
	capacity_w.sort()
	capacity_h.sort()
	if capacity_w == capacity_h:
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	counts = []
	for i in range(n):
		counts.append(0)
	colonnes = []
	for i in range(n):
		colonnes.append(0)
	for i in range(n):
		for j in range(n):
			colonnes[j] += M[i][j]
	t = True
	lignes = [sum(M[i]) for i in range(n)]
	sl = sorted(lignes)
	scol = sorted(colonnes)
	c = 0
	for i in range(n):
		if sl[i] != scol[i]:
			print('Impossible')
			c = 1
			break
	if c == 0:
		print('Possible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	possible = True
	sum_lines = []
	for i in range(n):
		line_cour = []
		for j in range(n):
			line_cour.append(M[i][j])
		sum_lines.append(sum(line_cour))
	sum_cols = []
	for i in range(n):
		col_cour = []
		for j in range(n):
			col_cour.append(M[j][i])
		sum_cols.append(sum(col_cour))
	sum_lines.sort()
	sum_cols.sort()
	if len(sum_lines) == len(sum_cols):
		for i in range(len(sum_lines)):
			if sum_lines[i] != sum_cols[i]:
				possible = False
				break
	else:
		possible = False
	if possible:
		print('Possible')
	else:
		print('Impossible')


for _ in range(int(input())):
	n = int(input())
	mat = [list(map(int, input().split())) for _ in range(n)]
	cont = [False] * n
	sums = [0] * n
	cons = [0] * n
	for i in range(n):
		for j in range(n):
			sums[j] += mat[i][j]
			cons[i] += mat[i][j]
	for i in range(n):
		for j in range(n):
			if cont[j] == False:
				if cons[i] - mat[i][j] == sums[j] - mat[i][j]:
					cont[j] = True
	if cont.count(True) == n:
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	c = []
	for i in range(n):
		c.append(sum(M[i]))
	c = sorted(c)
	t = []
	for j in range(n):
		v = 0
		for i in range(n):
			v += M[i][j]
		t.append(v)
	t = sorted(t)
	if t == c:
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	m = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		m.append(M_t)
	d = 0
	l = []
	for i in range(n):
		su = 0
		for j in range(n):
			su += m[j][i]
		l.append(su)
	for i in range(n):
		if sum(m[i]) not in l:
			d = 1
			break
		else:
			l.pop(l.index(sum(m[i])))
	if d == 1:
		print('Impossible')
	else:
		print('Possible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	containter_size_dict = {}
	for i in range(n):
		sum = 0
		for j in range(n):
			sum = sum + M[i][j]
		containter_size_dict[sum] = containter_size_dict.get(sum, 0) + 1
	list_balls = []
	for j in range(n):
		sum = 0
		for i in range(n):
			sum = sum + M[i][j]
		list_balls.append(sum)
	status = True
	for i in list_balls:
		if containter_size_dict.get(i, 0) > 0:
			containter_size_dict[i] = containter_size_dict[i] - 1
		else:
			status = False
			break
	if status == False:
		print('Impossible')
	else:
		print('Possible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	row_sum = []
	col_sum = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
		row_sum.append(sum(M_t))
	for i in range(n):
		s = 0
		for j in range(n):
			s += M[j][i]
		col_sum.append(s)
	row_sum = sorted(row_sum)
	col_sum = sorted(col_sum)
	i = 0
	for i in range(n):
		if row_sum[i] != col_sum[i]:
			break
	if i == n - 1:
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	Rows = []
	Cols = []
	Works = True
	for i in range(n):
		Rows.append(sum(M[i]))
	N = [list(i) for i in zip(*M)]
	for i in range(n):
		Cols.append(sum(N[i]))
	Rows.sort()
	Cols.sort()
	if Rows == Cols:
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	possible = True
	typeBalls = [0 for i in range(n)]
	capacity = [0 for i in range(n)]
	for i in range(n):
		for j in range(n):
			typeBalls[j] += M[i][j]
			capacity[i] += M[i][j]
	if sorted(typeBalls) == sorted(capacity):
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
		tb = []
		nc = []
	for i in range(n):
		sum = 0
		sum1 = 0
		for j in range(n):
			sum += M[j][i]
			sum1 += M[i][j]
		tb.append(sum)
		nc.append(sum1)
	p = 0
	for i in range(n):
		t = 0
		for j in range(n):
			avb = M[i][j]
			tball = tb[j]
			otball = nc[i] - avb
			rem = tball - avb
			if otball == rem:
				t = 1
		if t == 0:
			p = 1
			break
		else:
			p = 0
	if p == 0:
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	a = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		a.append(M_t)
	row = []
	col = []
	for i in range(n):
		sum1 = 0
		for j in range(n):
			sum1 += a[i][j]
		row.append(sum1)
	for i in range(n):
		sum1 = 0
		for j in range(n):
			sum1 += a[j][i]
		col.append(sum1)
	row.sort()
	col.sort()
	i = 0
	while i < n:
		if row[i] != col[i]:
			print('Impossible')
			break
		i += 1
	else:
		print('Possible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	row_sums = []
	column_sums = [0] * n
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		row_sums.append(sum(M_t))
		for j in range(n):
			column_sums[j] += M_t[j]
		M.append(M_t)
	print('Possible' if sorted(row_sums) == sorted(column_sums) else 'Impossible')


import sys

def sumColumn(m, column):
	total = 0
	for row in range(len(m)):
		total += m[row][column]
	return total
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	capacita = []
	for i in range(n):
		capacita.append(sum(M[i]))
	capacita = sorted(capacita)
	sumlist = []
	for i in range(n):
		sumlist.append(sumColumn(M, i))
	sumlist = sorted(sumlist)
	result = 0
	for i in range(n):
		if sumlist[i] > capacita[i]:
			print('Impossible')
			result = 1
			break
	if result == 0:
		print('Possible')


def build_matrix(n):
	mat = []
	for _ in range(n):
		mat.append([int(p) for p in input().split()])
	return mat
import sys

def find_best(l, needed):
	best = sys.maxsize
	b_idx = -1
	for idx in range(len(l)):
		capacity = l[idx][1]
		if capacity is None:
			continue
		if capacity >= needed:
			if capacity <= best:
				best = capacity
				b_idx = idx
		else:
			break
	if b_idx == -1:
		return None
	l[b_idx] = (None, None)
	return best
query = int(input())
for _ in range(query):
	n = int(input())
	occ = {}
	container_cap = {}
	max_num_c = n * n
	matrix = build_matrix(n)
	for (container, r) in enumerate(matrix):
		for (typ, num) in enumerate(r):
			if typ not in occ:
				occ[typ] = 0
			if container not in container_cap:
				container_cap[container] = 0
			occ[typ] += num
			container_cap[container] += num
	containers = list(reversed(sorted(container_cap.items(), key=lambda x: x[1])))
	numbbers = list(reversed(sorted(occ.items(), key=lambda x: x[1])))
	if len(numbbers) > len(containers):
		print('Impossible')
		continue
	IMPOSSIBLE = False
	for idx in range(len(containers)):
		con_cap = containers[idx][1]
		if con_cap is None:
			continue
		num_c = numbbers[idx][1]
		containers[idx] = (None, None)
		left = num_c - con_cap
		imp = False
		while left > 0:
			best_fit = find_best(containers, left)
			if best_fit is None:
				print('Impossible')
				imp = True
				IMPOSSIBLE = True
				break
			left -= best_fit
		if imp:
			break
		if num_c > con_cap:
			print('Impossible')
			IMPOSSIBLE = True
			break
	if not IMPOSSIBLE:
		print('Possible')


import sys
Q = int(input().strip())
for q in range(Q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	vertical_sums = set([])
	for j in range(n):
		res = 0
		for i in range(n):
			res += M[i][j]
		vertical_sums.add(res)
	horizontal_sums = set([])
	for i in range(n):
		res = sum(M[i])
		horizontal_sums.add(res)
	if vertical_sums == horizontal_sums:
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	cont_cap = []
	type_count = [0] * n
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		type_count = [a + b for (a, b) in zip(type_count, M_t)]
		cont_cap.append(sum(M_t))
		M.append(M_t)
	type_count.sort()
	cont_cap.sort()
	if all([a == b for (a, b) in zip(type_count, cont_cap)]):
		print('Possible')
	else:
		print('Impossible')


q = int(input())
for a0 in range(q):
	n = int(input())
	M = [[int(x) for x in input().split()] for i in range(n)]
	capa = sorted([sum(M[i]) for i in range(n)])
	bcount = [0] * n
	for i in range(n):
		for j in range(n):
			bcount[j] += M[i][j]
	bcount.sort()
	if capa == bcount:
		print('Possible')
	else:
		print('Impossible')


import sys

def isPossible(M):
	rsum = set([sum(r) for r in M])
	csum = set([sum(c) for c in zip(*M)])
	return len(rsum.union(csum)) == len(rsum)
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	if isPossible(M):
		print('Possible')
	else:
		print('Impossible')


from collections import defaultdict
c = 1
cases = int(input())
while c <= cases:
	n = int(input())
	m = []
	contc = [0 for i in range(0, n)]
	balls = [0 for i in range(0, n)]
	for i in range(0, n):
		m.append([int(i) for i in input().split()])
		for (ind, j) in enumerate(m[-1]):
			contc[i] += j
			balls[ind] += j
	pos = True
	if sorted(balls) != sorted(contc):
		pos = False
	if pos:
		print('Possible')
	else:
		print('Impossible')
	c = c + 1


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	size = [sum(i) for i in M]
	for i in range(n):
		sum1 = 0
		for j in M:
			sum1 += j[i]
		if sum1 in size:
			size.remove(sum1)
		else:
			break
	if len(size) == 0:
		print('Possible')
	else:
		print('Impossible')


def solve(M):
	rowssum = [sum(row) for row in M]
	colssum = [sum(col) for col in zip(*M)]
	return sorted(rowssum) == sorted(colssum)
for _ in range(int(input())):
	M = [list(map(int, input().split())) for i in range(int(input()))]
	print('Possible' if solve(M) else 'Impossible')


for q in range(int(input())):
	n = int(input())
	(r, c) = ([0] * n, [0] * n)
	for i in range(n):
		j = 0
		for x in input().split():
			y = int(x)
			r[i] += y
			c[j] += y
			j += 1
	ans = False
	for i in range(n):
		for j in range(n):
			if r[i] == c[j]:
				ans = True
				break
		if ans:
			break
	if ans:
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	sum_row_list = list()
	sum_col_list = list()
	flag = True
	for i in range(n):
		s = 0
		for j in range(n):
			s += M[i][j]
		sum_row_list.append(s)
	for i in range(n):
		s = 0
		for j in range(n):
			s += M[j][i]
		sum_col_list.append(s)
	sum_row_list.sort()
	sum_col_list.sort()
	for i in range(n):
		if sum_row_list[i] != sum_col_list[i]:
			flag = False
	if flag:
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	transposed = list(map(sum, [list(i) for i in zip(*M)]))
	i = 0
	while M:
		quantity = sum(M[i])
		flag = False
		j = 0
		for row in transposed:
			if quantity == row:
				M.pop(i)
				transposed.pop(j)
				i -= 1
				flag = True
			j += 1
		i += 1
		if not flag:
			print('Impossible')
			break
	if not M:
		print('Possible')


q = int(input().strip())
for a0 in range(q):
	a = 0
	size = []
	color = []
	c = 0
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	for i in range(n):
		a = 0
		for j in range(n):
			a += M[j][i]
		color.append(a)
	for ii in range(n):
		size.append(sum(M[ii]))
	color.sort(reverse=True)
	size.sort(reverse=True)
	for jj in range(n):
		if color[jj] > size[jj]:
			c += 1
	if c > 0:
		print('Impossible')
	else:
		print('Possible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	sums_ball = [0] * n
	sums_box = [0] * n
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		for i in range(n):
			sums_ball[i] = sums_ball[i] + M_t[i]
			sums_box[M_i] = sums_box[M_i] + M_t[i]
		M.append(M_t)
	sums_ball.sort()
	sums_box.sort()
	if sums_ball == sums_box:
		print('Possible')
	else:
		print('Impossible')


import sys

def solve(M):
	cont_sizes = {}
	for row in M:
		row_sum = sum(row)
		cont_sizes[row_sum] = cont_sizes.get(row_sum, 0) + 1
	type_sizes = {}
	for j in range(len(M[0])):
		col_sum = 0
		for i in range(len(M)):
			col_sum += M[i][j]
		type_sizes[col_sum] = type_sizes.get(col_sum, 0) + 1
	if cont_sizes == type_sizes:
		return 'Possible'
	return 'Impossible'
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	print(solve(M))


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	capacity = []
	tipos = [0] * n
	for i in range(n):
		capacity.append(sum(M[i]))
		for j in range(n):
			tipos[j] = tipos[j] + M[i][j]
	capacity = sorted(capacity)
	tipos = sorted(tipos)
	certo = True
	for i in range(n):
		if capacity[i] != tipos[i]:
			certo = False
			break
	if not certo:
		print('Impossible')
	else:
		print('Possible')


import sys

def sum_row(M, i, n):
	ans = 0
	for j in range(n):
		ans += M[i][j]
	return ans

def sum_col(M, i, n):
	ans = 0
	for j in range(n):
		ans += M[j][i]
	return ans
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	row = [0] * n
	col = [0] * n
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	flag = 0
	for i in range(n):
		row[i] = sum_row(M, i, n)
		col[i] = sum_col(M, i, n)
	if set(row) == set(col):
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	numballs = []
	c_size = []
	for i in range(n):
		numballs.append(sum((container[i] for container in M)))
		c_size.append(sum(M[i]))
	numballs.sort()
	c_size.sort()
	is_possible = 'Possible'
	for i in range(n):
		if numballs[i] > c_size[i]:
			is_possible = 'Impossible'
	print(is_possible)


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	type_sums = []
	type_sums += [0] * n
	cont_sums = []
	cont_sums += [0] * n
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
		type_sums = [type_sums[x] + M_t[x] for x in range(n)]
		cont_sums[M_i] = sum(M_t)
	for x in range(n):
		can_clear = False
		for y in range(n):
			if cont_sums[x] == type_sums[y]:
				can_clear = True
				break
		if can_clear == False:
			print('Impossible')
			break
	if can_clear == True:
		print('Possible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	balls = [0] * n
	box_size = [sum(x) for x in M]
	for box in M:
		for (i, ball) in enumerate(box):
			balls[i] += ball
	balls.sort()
	box_size.sort()
	res = 'Possible'
	for (i, j) in zip(balls, box_size):
		if not i == j:
			res = 'Impossible'
			break
	print(res)


import sys
q = int(input().strip())
for _ in range(q):
	n = int(input().strip())
	m = []
	s = []
	for __ in range(n):
		tmp = list(map(int, input().strip().split(' ')))
		m.append(tmp)
		s.append(sum(tmp))
	ss = []
	for x in list(zip(*m)):
		ss.append(sum(x))
	s.sort()
	ss.sort()
	if ss == s:
		print('Possible')
	else:
		print('Impossible')


q = int(input())
for _ in range(q):
	n = int(input())
	M = [[int(x) for x in input().split()] for _ in range(n)]
	a = sorted([sum(x) for x in M])
	b = sorted([sum(x) for x in zip(*M)])
	if a == b:
		print('Possible')
	else:
		print('Impossible')


tests = int(input())
for test in range(tests):
	n = int(input())
	sr = [0] * n
	sc = [0] * n
	for i in range(n):
		row = list(map(int, input().split(' ')))
		for j in range(n):
			sr[i] += row[j]
			sc[j] += row[j]
	print('Possible' if sorted(sr) == sorted(sc) else 'Impossible')


import collections
for _ in range(int(input())):
	M = [[int(m) for m in input().split()] for _ in range(int(input()))]
	Mt = zip(*M)
	C = collections.Counter(map(sum, M))
	Ct = collections.Counter(map(sum, Mt))
	print('Possible' if C == Ct else 'Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	containerCounts = [0] * n
	typeCounts = [0] * n
	for rowCount in range(n):
		row = [int(M_temp) for M_temp in input().strip().split(' ')]
		containerCount = 0
		for columnCount in range(n):
			typeCounts[columnCount] += row[columnCount]
			containerCount += row[columnCount]
		containerCounts[rowCount] = containerCount
	if sorted(typeCounts) == sorted(containerCounts):
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	ball = list(map(sum, M))
	container = [sum(list(map(lambda x: x[i], M))) for i in range(n)]
	ball = sorted(ball)
	container = sorted(container)
	if all(map(lambda x: x[0] == x[1], zip(ball, container))):
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	rowSums = []
	colSums = []
	for i in range(n):
		rowSums.append(sum(M[i]))
	for i in range(n):
		colSum = 0
		for j in range(n):
			colSum += M[j][i]
		colSums.append(colSum)
	if sorted(rowSums) == sorted(colSums):
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	types = len(M[0])
	cont = len(M)
	cap = []
	su = []
	for i in M:
		g = 0
		for j in i:
			g = g + int(j)
		cap.append(g)
	for i in range(types):
		s = 0
		for j in range(cont):
			s = s + M[j][i]
		su.append(s)
	cap.sort()
	su.sort()
	if su == cap:
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	lr = []
	lc = []
	for i in M:
		lr.append(sum(i))
	for i in range(0, n, 1):
		su = 0
		for j in range(0, n, 1):
			su = su + M[j][i]
		lc.append(su)
	lr.sort()
	lc.sort()
	if lr == lc:
		print('Possible')
	else:
		print('Impossible')


tests = int(input())
for test in range(tests):
	n = int(input())
	sr = [0] * n
	sc = [0] * n
	for i in range(n):
		row = list(map(int, input().split()))
		for j in range(n):
			sr[i] += row[j]
			sc[j] += row[j]
	print('Possible' if sorted(sr) == sorted(sc) else 'Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	a = sorted([sum(v) for v in M])
	b = sorted([sum((l[i] for l in M)) for i in range(n)])
	try:
		next((v1 for (v1, v2) in zip(a, b) if v1 != v2))
		print('Impossible')
	except:
		print('Possible')


import sys
q = int(input().strip())
for _ in range(q):
	n = int(input().strip())
	a = []
	for _ in range(n):
		ip = list(map(int, input().strip().split(' ')))
		a.append(ip)
	balls_c = [0 for _ in range(n)]
	balls_t = [0 for _ in range(n)]
	for c in range(n):
		balls_c[c] = sum(a[c])
	for c in range(n):
		for t in range(n):
			balls_t[t] += a[c][t]
	balls_c.sort()
	balls_t.sort()
	if balls_c == balls_t:
		print('Possible')
	else:
		print('Impossible')


q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	rowSums = []
	colSums = []
	for i in range(n):
		rowSums.append(sum(M[i]))
	for i in range(n):
		colSum = 0
		for j in range(n):
			colSum += M[j][i]
		colSums.append(colSum)
	if sorted(rowSums) == sorted(colSums):
		print('Possible')
	else:
		print('Impossible')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	rows = []
	cols = [0 for i in range(n)]
	for M_i in range(n):
		row = [int(x) for x in input().split()]
		rows.append(sum(row))
		for i in range(n):
			cols[i] += row[i]
	print('Possible' if sorted(cols) == sorted(rows) else 'Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	counts = [0] * n
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
		for i in range(n):
			counts[i] += M_t[i]
	if all(map(lambda x: x[0] == x[1], zip(sorted(counts), sorted(list(map(sum, M)))))):
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	print('Possible') if sorted([sum(i) for i in M]) == sorted([sum([M[j][i] for j in range(len(M))]) for i in range(len(M))]) else print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	container = []
	types = [0] * n
	for i in range(n):
		container.append(sum(M[i]))
		for j in range(n):
			types[i] += M[j][i]
	container.sort()
	types.sort()
	flag = True
	for i in range(n):
		if container[i] != types[i]:
			flag = False
			break
	if flag:
		print('Possible')
	else:
		print('Impossible')


def get_all_balls(bins):
	all_balls = [0] * len(bins)
	for bin in bins:
		for ball_id in range(len(bin)):
			all_balls[ball_id] += bin[ball_id]
	return all_balls

def solution(input):
	T = int(input())
	for case in range(T):
		bins = []
		N = int(input())
		for n in range(N):
			bins.append([int(tmp) for tmp in input().split()])
		all_balls = get_all_balls(bins)
		for ball_id in range(N):
			fitting_bin_found = False
			for bin in bins:
				if all_balls[ball_id] == sum(bin):
					fitting_bin_found = True
					break
			if not fitting_bin_found:
				break
		print('Possible' if fitting_bin_found else 'Impossible')
solution(input)


q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	matrix = [list(map(int, input().strip().split(' '))) for _ in range(n)]
	ball_counts = [0] * n
	container_sizes = []
	for row in matrix:
		container_sizes.append(sum(row))
		for (index, num_balls) in enumerate(row):
			ball_counts[index] += num_balls
	if sorted(ball_counts) == sorted(container_sizes):
		print('Possible')
	else:
		print('Impossible')


for __ in range(int(input())):
	n = int(input())
	M = [[int(quantity) for quantity in input().split()] for __ in range(n)]
	row_sum = sorted((sum(row) for row in M))
	column_sum = sorted((sum(column) for column in zip(*M)))
	print('Possible' if row_sum == column_sum else 'Impossible')


import sys

def column(matrix, i):
	return [row[i] for row in matrix]
for _ in range(int(input())):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	buckets = [sum(row) for row in M]
	balls = [sum(column(M, i)) for i in range(n)]
	if sorted(buckets) == sorted(balls):
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	rowsum = [0] * n
	colsum = [0] * n
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
		rowsum[M_i] = sum(M[-1])
		colsum = list(map(lambda a, b: a + b, colsum, M[-1]))
	rowsum.sort()
	colsum.sort()
	if rowsum == colsum:
		print('Possible')
	else:
		print('Impossible')


import sys

def organize(balls, bowls):
	for i in range(len(bowls)):
		if balls[i] not in bowls:
			return False
	return True
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	balls = {}
	bowls = []
	for i in range(n):
		balls[i] = 0
	for bowl in M:
		for i in range(n):
			balls[i] += bowl[i]
		bowls.append(sum(bowl))
	if organize(balls, bowls):
		print('Possible')
	else:
		print('Impossible')


def solve(M):
	return sorted(map(sum, M)) == sorted(map(sum, zip(*M)))
q = int(input())
for _ in range(q):
	n = int(input())
	M = tuple((tuple(map(int, input().split())) for _ in range(n)))
	if solve(M):
		print('Possible')
	else:
		print('Impossible')


q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	rowSums = []
	colSums = []
	for i in range(n):
		rowSums.append(sum(M[i]))
	for i in range(n):
		colSum = 0
		for j in range(n):
			colSum += M[j][i]
		colSums.append(colSum)
	if sorted(rowSums) == sorted(colSums):
		print('Possible')
	else:
		print('Impossible')


import sys

def calculate_swaps(matrix):
	container_sizes = [sum((elt for elt in container)) for container in matrix]
	group_sizes = [sum((elt for elt in kind)) for kind in zip(*matrix)]
	return sorted(container_sizes) == sorted(group_sizes)
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	if calculate_swaps(M):
		print('Possible')
	else:
		print('Impossible')


def readInts():
	return map(int, input().strip().split())

def try_fit(n, m):
	sizes = []
	for container in range(n):
		c_size = sum((m[container][b] for b in range(n)))
		sizes.append(c_size)
	counts = []
	for btype in range(n):
		t_count = sum((m[c][btype] for c in range(n)))
		counts.append(t_count)
	sizes.sort()
	counts.sort()
	can_fit = True
	for i in range(n):
		if sizes[i] != counts[i]:
			can_fit = False
			break
	if can_fit:
		print('Possible')
	else:
		print('Impossible')
	return
q = list(readInts())[0]
for _ in range(q):
	n = list(readInts())[0]
	m = []
	for row in range(n):
		m.append(list(readInts()))
	try_fit(n, m)


import sys

def sumcol(A, col, n):
	sum = 0
	for i in range(n):
		sum += A[i][col]
	return sum
q = int(input())
for _ in range(q):
	n = int(input())
	M = []
	for _ in range(n):
		M_t = list(map(int, input().split()))
		M.append(M_t)
	typesum = []
	contsum = []
	for i in range(n):
		typesum.append(sum(M[i]))
		contsum.append(sumcol(M, i, n))
	if sorted(typesum) == sorted(contsum):
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	cs = [0] * n
	rs = [0] * n
	for i in range(n):
		r = [int(x) for x in input().strip().split(' ')]
		cs = [x + y for (x, y) in zip(cs, r)]
		rs[i] = sum(r)
	rs.sort()
	cs.sort()
	print('Possible' if rs == cs else 'Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	r = sorted([sum([row[i] for row in M]) for i in range(0, len(M[0]))])
	c = sorted([sum(M[i]) for i in range(len(M))])
	if r == c:
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	sums = dict()
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	rowsum = [sum(x) for x in M]
	colsum = [sum((x[i] for x in M)) for i in range(n)]
	for x in rowsum:
		if sums.get(x, -1) == -1:
			sums[x] = 1
		else:
			sums[x] += 1
	for y in colsum:
		if sums.get(y, -1) == -1 or sums[y] == 0:
			print('Impossible')
			break
		else:
			sums[y] -= 1
	else:
		print('Possible')


for _ in range(int(input())):
	n = int(input())
	(types, bins) = ([0 for _ in range(n)], [])
	for _ in range(n):
		row = list(map(int, input().split()))
		types = list(map(sum, zip(row, types)))
		bins.append(sum(row))
	types.sort()
	bins.sort()
	if types == bins:
		print('Possible')
	else:
		print('Impossible')


for _ in range(int(input())):
	l = [list(map(int, input().split())) for _ in range(int(input()))]
	r = [sum([j for j in i]) for i in l]
	s = 'Possible'
	for i in range(len(r)):
		c = sum([j[i] for j in l])
		if c in r:
			r.remove(c)
		else:
			s = 'Impossible'
			break
	print('{:s}'.format(s))


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	rowSums = []
	colSums = []
	for i in range(n):
		rowSums.append(sum(M[i]))
	for i in range(n):
		colSum = 0
		for j in range(n):
			colSum += M[j][i]
		colSums.append(colSum)
	if sorted(rowSums) == sorted(colSums):
		print('Possible')
	else:
		print('Impossible')


import operator
q = int(input().strip())
for _ in range(q):
	n = int(input().strip())
	size_count = []
	type_count = [0] * n
	for _ in range(n):
		ball_types = list(map(int, input().strip().split(' ')))
		type_count = list(map(operator.add, type_count, ball_types))
		size_count.append(sum(ball_types))
	if sorted(size_count) == sorted(type_count):
		print('Possible')
	else:
		print('Impossible')


q = int(input())
for _ in range(q):
	n = int(input())
	matrix = []
	cont_sum = []
	type_sum = []
	for i in range(n):
		matrix.append([int(i) for i in input().split(' ')])
	for i in range(n):
		cont_sum.append(sum(matrix[i]))
		temp = 0
		for j in range(n):
			temp += matrix[j][i]
		type_sum.append(temp)
	if sorted(cont_sum) != sorted(type_sum):
		print('Impossible')
	else:
		print('Possible')


q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	row_sum = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
		row_sum.append(sum(M_t))
	col_sum = []
	for col in range(n):
		sum1 = 0
		for row in M:
			sum1 += row[col]
		col_sum.append(sum1)
	if sorted(row_sum) == sorted(col_sum):
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	cans = sorted([sum(row) for row in M])
	balls = sorted([sum(row) for row in zip(*M)])
	for (c, b) in zip(cans, balls):
		if c != b:
			print('Impossible')
			break
	else:
		print('Possible')


import sys

def sumColumn(m, column):
	total = 0
	for row in range(len(m)):
		total += m[row][column]
	return total
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	capacita = []
	for i in range(n):
		capacita.append(sum(M[i]))
	capacita = sorted(capacita)
	sumlist = []
	for i in range(n):
		sumlist.append(sumColumn(M, i))
	sumlist = sorted(sumlist)
	result = 0
	for i in range(n):
		if sumlist[i] > capacita[i]:
			print('Impossible')
			result = 1
			break
	if result == 0:
		print('Possible')


import sys

def check(matrix):
	l = len(matrix)
	types = l * [0]
	buckets = l * [0]
	for j in range(l):
		for i in range(l):
			types[j] += matrix[i][j]
			buckets[i] += matrix[i][j]
	for t in types:
		buckets = [x for x in buckets if not x == t]
	return len(buckets) == 0
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	if check(M):
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	TraceCols = []
	TraceRows = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		TraceRows.append(sum(M_t))
		M.append(M_t)
	for i in range(n):
		TraceCols.append(sum([M[j][i] for j in range(n)]))
	for i in range(n):
		if TraceCols[i] in TraceRows:
			TraceRows.remove(TraceCols[i])
		else:
			print('Impossible')
			break
	if TraceRows == []:
		print('Possible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	row_sums = [sum(row) for row in M]
	col_sums = [sum((M[row_idx][col_idx] for row_idx in range(n))) for col_idx in range(n)]
	print('Possible' if sorted(row_sums) == sorted(col_sums) else 'Impossible')


for i in range(int(input())):
	size = int(input())
	columnas = [0 for e in range(size)]
	filas = []
	razon = True
	for e in range(size):
		lista = [int(g) for g in input().split()]
		filas.append(sum(lista))
		for d in range(size):
			columnas[d] += lista[d]
	filas.sort()
	columnas.sort()
	for e in range(size):
		if columnas[e] != filas[e]:
			razon = False
			break
	if razon:
		print('Possible')
	else:
		print('Impossible')


n = int(input())
for a0 in range(n):
	m = int(input())
	b = []
	rowsum = []
	colsum = []
	for a in range(m):
		a = [int(temp) for temp in input().strip().split(' ')]
		b.append(a)
		rowsum.append(sum(a))
	t = list(map(list, zip(*b)))
	for i in t:
		colsum.append(sum(i))
	colsum.sort()
	rowsum.sort()
	if colsum == rowsum:
		print('Possible')
	else:
		print('Impossible')


import sys
nq = int(input().strip())
for _ in range(nq):
	n = int(input().strip())
	matrix = []
	for container in range(n):
		matrix.append(list(map(int, input().strip().split())))
	containerSums = [0] * n
	typeSums = [0] * n
	for i in range(n):
		containerSums[i] = sum(matrix[i])
		for j in range(n):
			typeSums[i] += matrix[j][i]
	containerSums.sort()
	typeSums.sort()
	if containerSums == typeSums:
		print('Possible')
	else:
		print('Impossible')


import sys
import array

class Bag:

	def __init__(self):
		self.table = {}

	def add(self, item):
		if item in self.table:
			self.table[item] += 1
		else:
			self.table[item] = 1

	def __eq__(self, other):
		for item in self.table:
			if not item in other.table:
				return False
			if self.table[item] != other.table[item]:
				return False
		for item in other.table:
			if not item in self.table:
				return False
		return True

	def __ne__(self, other):
		return not self.__eq__(other)

def container_size_bag(m):
	bag = Bag()
	for row in m:
		bag.add(sum(row))
	return bag

def ball_count_bag(m):
	bag = Bag()
	for i_column in range(len(m)):
		count = 0
		for row in m:
			count += row[i_column]
		bag.add(count)
	return bag

def is_possible(m):
	return container_size_bag(m) == ball_count_bag(m)
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	if is_possible(M):
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	A = []
	possible = True
	for m in M:
		A.append(sum(m))
	M = zip(*M)
	B = []
	for m in M:
		B.append(sum(m))
	if sorted(A) == sorted(B):
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	retour = 'Possible'
	for i in range(n):
		test = 'KO'
		for j in range(n):
			if sum(M[i]) == sum([M[k][j] for k in range(n)]):
				test = 'OK'
				break
		if test == 'OK':
			continue
		else:
			retour = 'Impossible'
			break
	print(retour)


for i in range(int(input())):
	(a, n) = ([], int(input()))
	for i in range(n):
		a += [list(map(int, input().split()))]
	(i, b1, b2) = (0, [], [])
	while i < n:
		c1 = c2 = 0
		for j in range(n):
			c1 += a[i][j]
			c2 += a[j][i]
		b1 += [c1]
		b2 += [c2]
		i += 1
	b1.sort()
	b2.sort()
	if b1 != b2:
		print('Impossible')
	else:
		print('Possible')


for _ in range(int(input())):
	n = int(input())
	c = [0] * n
	b = [0] * n
	for i in range(n):
		for (x, y) in enumerate(list(map(int, input().split()))):
			b[x] += y
			c[i] += y
	for i in range(n):
		if c[i] in b:
			b.remove(c[i])
		else:
			print('Impossible')
			break
	else:
		print('Possible')


import sys

def sort(a):
	c = []
	for ai in a:
		i = 0
		while i < len(c):
			if ai < c[i]:
				c.insert(i, ai)
				i = len(a) + 10
			i += 1
		if i == len(c):
			c.append(ai)
	return c
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	a = []
	for i in range(n):
		a.append(0)
		for j in range(n):
			a[i] += M[i][j]
	b = []
	for j in range(n):
		b.append(0)
		for i in range(n):
			b[j] += M[i][j]
	a = sort(a)
	b = sort(b)
	if a == b:
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	if sorted([sum(line) for line in M]) == sorted([sum([line[i] for line in M]) for i in range(n)]):
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	bucketSizes = [0] * n
	typeCounts = [0] * n
	for i in range(n):
		bucket = [int(M_temp) for M_temp in input().strip().split(' ')]
		bucketSizes[i] = sum(bucket)
		for i in range(n):
			typeCounts[i] += bucket[i]
	if sorted(typeCounts) == sorted(bucketSizes):
		print('Possible')
	else:
		print('Impossible')


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	sum_rows = []
	sum_cols = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
	for col in range(n):
		ball_type = 0
		for row in range(n):
			ball_type += M[row][col]
		sum_cols.append(ball_type)
		sum_rows.append(sum(M[col]))
	if sorted(sum_rows) == sorted(sum_cols):
		print('Possible')
	else:
		print('Impossible')


q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	M = []
	k = []
	l = []
	for M_i in range(n):
		M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
		M.append(M_t)
		k.append(sum(M_t))
	for i in range(n):
		s = 0
		for j in range(n):
			s += M[j][i]
		l.append(s)
	if sorted(l) == sorted(k):
		print('Possible')
	else:
		print('Impossible')


for _ in range(int(input())):
	m = []
	rows = []
	cols = []
	n = int(input())
	for __ in range(n):
		m.append([int(___) for ___ in input().split()])
	for i in range(n):
		rows.append(sum(m[i]))
	for i in range(n):
		x = 0
		for j in range(n):
			x += m[j][i]
		cols.append(x)
	if sorted(rows) == sorted(cols):
		print('Possible')
	else:
		print('Impossible')


def judge(M):
	container_list = sorted([sum(x) for x in M])
	ball_list = sorted([sum(type_list) for type_list in zip(*M)])
	if container_list == ball_list:
		return True
	else:
		return False
for _ in range(int(input())):
	n = int(input())
	M = []
	for _ in range(n):
		M.append([int(z) for z in input().split(' ')])
	print('Possible' if judge(M) else 'Impossible')