Given a number of friends who have to give or take some amount of money from one another. Design an algorithm by which the total cash flow among all the friends is minimized. 
Example 1:
Input:
N=3
transaction [][]={{0,100,0}, {0,0,100}, {100,0,0}}
Output:
transaction [][]={{0,0,0},{0,0,0},{0,0,0}}
Explanation:
Since friend one has to give friend two which has to give friend three and which in turn has to give one. So it is better than no one will do anything to anyone.
Example 2:
Input:
N=3
transaction [][]={{0,100,0{,{0,0,200},{0,0,0}}
Output:
transaction [][]={0,0,100},{0,0,100},{0,0,0}
Explanation:
The net flow is minimized.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minCashFlow() which takes the transaction array and number of friends as input parameters and returns the new transaction array as output;.
 
 
Expected Time Complexity: O(N*N)
Expected Auxiliary Space: O(N*N)
 
Constraints:
1 <= N <= 1000
0^{ }<= transactio[i][j] <= 1000

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: from typing import List





class Solution:

    def minCashFlow(self, n : int, g : List[List[int]]) -> List[List[int]]:

        # code here

        



Solutions:
from typing import List

class Solution:

	def minCashFlow(self, n, arr):
		n = len(arr)
		optArr = [[0 for i in range(n)] for j in range(n)]
		graph = [[] for i in range(n)]
		amounts = [0 for i in range(n)]
		for i in range(n):
			for j in range(n):
				if arr[i][j]:
					graph[i].append([j, arr[i][j]])
		for i in range(n):
			curLen = len(graph[i])
			for j in range(curLen):
				amounts[i] -= graph[i][j][1]
				amounts[graph[i][j][0]] += graph[i][j][1]
		for i in range(n):
			maxCredit = 0
			maxDebit = 0
			ci = None
			di = None
			for i in range(len(amounts)):
				if amounts[i] > maxCredit:
					ci = i
					maxCredit = amounts[i]
				if amounts[i] < maxDebit:
					di = i
					maxDebit = amounts[i]
			if maxCredit and maxDebit:
				if maxCredit >= abs(maxDebit):
					optArr[di][ci] = abs(maxDebit)
					amounts[di] = 0
					amounts[ci] -= abs(maxDebit)
				else:
					optArr[di][ci] = maxCredit
					amounts[di] += maxCredit
					amounts[ci] = 0
		return optArr


from typing import List

class Solution:

	def minCashFlow(self, n: int, g: List[List[int]]) -> List[List[int]]:
		t = [[0 for i in range(n)] for j in range(n)]
		netAmount = [0 for i in range(n)]
		for p in range(n):
			for i in range(n):
				netAmount[p] += g[i][p] - g[p][i]
		while True:
			maxCredit = max(netAmount)
			pcredit = netAmount.index(maxCredit)
			maxDebit = min(netAmount)
			pdebit = netAmount.index(maxDebit)
			if maxCredit == 0 and maxDebit == 0:
				break
			min_ = min(abs(maxCredit), abs(maxDebit))
			netAmount[pcredit] -= min_
			netAmount[pdebit] += min_
			t[pdebit][pcredit] = min_
		return t


from typing import List

class Solution:

	def minCashFlow(self, n: int, g: List[List[int]]) -> List[List[int]]:
		netamt = [0] * n
		for person in range(0, n):
			for another in range(0, n):
				netamt[person] -= g[person][another]
				netamt[another] += g[person][another]

		def getmax():
			maxidx = 0
			for i in range(1, n):
				if netamt[i] > netamt[maxidx]:
					maxidx = i
			return maxidx

		def getmin():
			minidx = 0
			for i in range(1, n):
				if netamt[i] < netamt[minidx]:
					minidx = i
			return minidx
		out = [[0] * n for i in range(n)]

		def solve(netamt):
			minnet = getmin()
			maxnet = getmax()
			if netamt[minnet] == 0 and netamt[maxnet] == 0:
				return
			minamt = -netamt[minnet] if -netamt[minnet] < netamt[maxnet] else netamt[maxnet]
			netamt[minnet] += minamt
			netamt[maxnet] -= minamt
			out[minnet][maxnet] = minamt
			solve(netamt)
		solve(netamt)
		return out


from typing import List

class Solution:

	def helper(self, rem, trans):
		(maxi, mini) = (rem.index(max(rem)), rem.index(min(rem)))
		if rem[maxi] == 0 or rem[mini] == 0:
			return
		temp = min(-rem[mini], rem[maxi])
		rem[maxi] -= temp
		rem[mini] += temp
		trans[mini][maxi] = temp
		self.helper(rem, trans)

	def minCashFlow(self, n: int, g: List[List[int]]) -> List[List[int]]:
		rem = [0 for i in range(n)]
		for i in range(n):
			for j in range(n):
				rem[i] += g[j][i] - g[i][j]
		trans = [[0] * n for i in range(n)]
		self.helper(rem, trans)
		return trans


from typing import List

class Solution:

	def getMin(self, netAmount):
		idx = 0
		n = len(netAmount)
		for i in range(1, n):
			if netAmount[i] < netAmount[idx]:
				idx = i
		return idx

	def getMax(self, netAmount):
		idx = 0
		for i in range(1, n):
			if netAmount[i] > netAmount[idx]:
				idx = i
		return idx

	def minCashFlow(self, n: int, g: List[List[int]]) -> List[List[int]]:
		netAmount = [0] * n
		for i in range(n):
			for j in range(n):
				netAmount[i] += g[j][i] - g[i][j]
		zeros = 0
		for p in range(n):
			if netAmount[p] == 0:
				zeros += 1
		transaction = [[0 for _ in range(n)] for _ in range(n)]
		while zeros != n:
			min_amount_idx = self.getMin(netAmount)
			max_amount_idx = self.getMax(netAmount)
			if netAmount[max_amount_idx] > abs(netAmount[min_amount_idx]):
				netAmount[max_amount_idx] = netAmount[max_amount_idx] - abs(netAmount[min_amount_idx])
				transaction[min_amount_idx][max_amount_idx] = abs(netAmount[min_amount_idx])
				netAmount[min_amount_idx] = 0
			elif netAmount[max_amount_idx] < abs(netAmount[min_amount_idx]):
				netAmount[min_amount_idx] = netAmount[min_amount_idx] + netAmount[max_amount_idx]
				transaction[min_amount_idx][max_amount_idx] = netAmount[max_amount_idx]
				netAmount[max_amount_idx] = 0
			else:
				netAmount[max_amount_idx] = 0
				transaction[min_amount_idx][max_amount_idx] = abs(netAmount[min_amount_idx])
				netAmount[min_amount_idx] = 0
			zeros += 1
		return transaction


from typing import List

class Solution:

	def get_min(self, net_amount):
		min_amount_idx = 0
		for p in range(1, n):
			if net_amount[p] < net_amount[min_amount_idx]:
				min_amount_idx = p
		return min_amount_idx

	def get_max(self, net_amount):
		max_amount_idx = 0
		for p in range(1, n):
			if net_amount[p] > net_amount[max_amount_idx]:
				max_amount_idx = p
		return max_amount_idx

	def minCashFlow(self, n: int, g: List[List[int]]) -> List[List[int]]:
		net_amount = [0] * n
		for p in range(n):
			for i in range(n):
				net_amount[p] += g[i][p] - g[p][i]
		num_of_zeros = 0
		for p in range(n):
			if net_amount[p] == 0:
				num_of_zeros += 1
		transaction = [[0 for _ in range(n)] for _ in range(n)]
		while num_of_zeros != n:
			min_amount_idx = self.get_min(net_amount)
			max_amount_idx = self.get_max(net_amount)
			if net_amount[max_amount_idx] > abs(net_amount[min_amount_idx]):
				net_amount[max_amount_idx] = net_amount[max_amount_idx] - abs(net_amount[min_amount_idx])
				transaction[min_amount_idx][max_amount_idx] = abs(net_amount[min_amount_idx])
				net_amount[min_amount_idx] = 0
			elif net_amount[max_amount_idx] < abs(net_amount[min_amount_idx]):
				net_amount[min_amount_idx] = net_amount[min_amount_idx] + net_amount[max_amount_idx]
				transaction[min_amount_idx][max_amount_idx] = net_amount[max_amount_idx]
				net_amount[max_amount_idx] = 0
			else:
				net_amount[max_amount_idx] = 0
				transaction[min_amount_idx][max_amount_idx] = abs(net_amount[min_amount_idx])
				net_amount[min_amount_idx] = 0
			num_of_zeros += 1
		return transaction


from typing import List

class Solution:

	def __init__(self):
		self.ans = [[0 for j in range(n)] for i in range(n)]

	def minCashFlowRec(self, amount, n):
		maxInd = 0
		for i in range(1, n):
			if amount[i] > amount[maxInd]:
				maxInd = i
		mxCredit = maxInd
		minInd = 0
		for i in range(1, n):
			if amount[i] < amount[minInd]:
				minInd = i
		mxDebit = minInd
		if amount[mxCredit] == 0 and amount[mxDebit] == 0:
			return 0
		mini = min(-amount[mxDebit], amount[mxCredit])
		amount[mxCredit] -= mini
		amount[mxDebit] += mini
		self.ans[mxCredit][mxDebit] += mini
		self.minCashFlowRec(amount, n)

	def minCashFlow(self, n: int, g: List[List[int]]) -> List[List[int]]:
		amount = [0 for i in range(n)]
		for p in range(n):
			for i in range(n):
				amount[p] += g[p][i] - g[i][p]
		self.minCashFlowRec(amount, n)
		return self.ans


from typing import List
from heapq import heappush as push, heappop as pop

class Solution:

	def minCashFlow(self, n: int, y: List[List[int]]) -> List[List[int]]:
		x = [0 for i in range(n)]
		for i in range(n):
			for j in range(n):
				x[i] -= y[i][j]
				x[j] += y[i][j]
				y[i][j] = 0
		q_max = []
		q_min = []
		for i in range(n):
			if x[i] > 0:
				push(q_min, (-x[i], i))
			elif x[i] < 0:
				push(q_max, (x[i], i))
		ans = 0
		while q_min and q_max:
			(a, b) = pop(q_min)
			(c, d) = pop(q_max)
			if abs(a) < abs(c):
				y[d][b] += abs(a)
				push(q_max, (-(abs(c) - abs(a)), d))
			elif abs(a) > abs(c):
				y[d][b] += abs(c)
				push(q_min, (abs(c) - abs(a), b))
			else:
				y[d][b] += abs(c)
		return y


from typing import List

class Solution:

	def minCashFlow(self, n: int, g: List[List[int]]) -> List[List[int]]:

		def getMin(arr):
			minInd = 0
			for i in range(1, n):
				if arr[i] < arr[minInd]:
					minInd = i
			return minInd

		def getMax(arr):
			maxInd = 0
			for i in range(1, n):
				if arr[i] > arr[maxInd]:
					maxInd = i
			return maxInd

		def minCashFlowRec(amount):
			mxCredit = getMax(amount)
			mxDebit = getMin(amount)
			if amount[mxCredit] == 0 and amount[mxDebit] == 0:
				return 0
			mini = min(-amount[mxDebit], amount[mxCredit])
			amount[mxCredit] -= mini
			amount[mxDebit] += mini
			g[mxDebit][mxCredit] += mini
			minCashFlowRec(amount)
		net = [0] * n
		for i in range(n):
			for j in range(n):
				net[i] -= g[i][j]
				net[j] += g[i][j]
				g[i][j] = 0
		minCashFlowRec(net)
		return g


from typing import List

class Solution:

	def mini(self, arr):
		idx = 0
		for i in range(1, len(arr)):
			if arr[i] < arr[idx]:
				idx = i
		return idx

	def maxi(self, arr):
		idx = 0
		for i in range(1, len(arr)):
			if arr[i] > arr[idx]:
				idx = i
		return idx

	def solve(self, arr, graph):
		minidx = self.mini(arr)
		maxidx = self.maxi(arr)
		if arr[minidx] == 0 and arr[maxidx] == 0:
			return 0
		minimum = min(-arr[minidx], arr[maxidx])
		arr[minidx] += minimum
		arr[maxidx] -= minimum
		graph[minidx][maxidx] = minimum
		self.solve(arr, graph)

	def minCashFlow(self, n: int, graph: List[List[int]]) -> List[List[int]]:
		persons = [0] * n
		for i in range(n):
			for j in range(n):
				persons[i] += graph[j][i] - graph[i][j]
		ans = [[0 for i in range(n)] for j in range(n)]
		self.solve(persons, ans)
		return ans


from typing import List

def getIofMaxCred(a):
	max = a[0]
	index = 0
	for i in range(len(a)):
		if a[i] > max:
			max = a[i]
			index = i
	return index

def getIofMaxDeb(a):
	min = a[0]
	index = 0
	for i in range(len(a)):
		if a[i] < min:
			min = a[i]
			index = i
	return index

def solve(amount, ans):
	md = getIofMaxDeb(amount)
	mc = getIofMaxCred(amount)
	if amount[md] == 0 and amount[mc] == 0:
		return 0
	amntmin = min(-amount[md], amount[mc])
	amount[mc] -= amntmin
	amount[md] += amntmin
	ans[md][mc] = amntmin
	solve(amount, ans)

class Solution:

	def minCashFlow(self, n: int, g: List[List[int]]) -> List[List[int]]:
		amount = [0 for i in range(n)]
		for i in range(n):
			for j in range(n):
				amount[i] += g[j][i] - g[i][j]
		ans = [[0 for i in range(n)] for i in range(n)]
		solve(amount, ans)
		return ans


from typing import List

class Solution:

	def minCashFlow(self, n: int, g: List[List[int]]) -> List[List[int]]:

		def find_min_ind(amt):
			ans = amt[0]
			ans_ind = 0
			for i in range(n):
				if ans > amt[i]:
					ans = amt[i]
					ans_ind = i
			return ans_ind

		def find_max_ind(amt):
			ans = amt[0]
			ans_ind = 0
			for i in range(n):
				if ans < amt[i]:
					ans = amt[i]
					ans_ind = i
			return ans_ind
		amount = [0] * n
		for i in range(n):
			for j in range(n):
				amount[i] += g[j][i] - g[i][j]
		ans = [[0 for i in range(n)] for j in range(n)]
		while True:
			min_ind = find_min_ind(amount)
			max_ind = find_max_ind(amount)
			if amount[min_ind] == 0 and amount[max_ind] == 0:
				return ans
			else:
				min_val = min(abs(amount[min_ind]), amount[max_ind])
				ans[min_ind][max_ind] = min_val
				amount[min_ind] += min_val
				amount[max_ind] -= min_val

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		g = IntMatrix().Input(n, n)
		obj = Solution()
		res = obj.minCashFlow(n, g)
		IntMatrix().Print(res)


from typing import List

def getIofMaxCred(a):
	max = a[0]
	index = 0
	for i in range(len(a)):
		if a[i] > max:
			max = a[i]
			index = i
	return index

def getIofMaxDeb(a):
	min = a[0]
	index = 0
	for i in range(len(a)):
		if a[i] < min:
			min = a[i]
			index = i
	return index

def solve(amount, ans):
	md = getIofMaxDeb(amount)
	mc = getIofMaxCred(amount)
	if amount[md] == 0 and amount[mc] == 0:
		return 0
	amntmin = min(-amount[md], amount[mc])
	amount[mc] -= amntmin
	amount[md] += amntmin
	ans[md][mc] = amntmin
	solve(amount, ans)

class Solution:

	def minCashFlow(self, n: int, g: List[List[int]]) -> List[List[int]]:
		amount = [0 for i in range(n)]
		for i in range(n):
			for j in range(n):
				amount[i] += g[j][i] - g[i][j]
		ans = [[0 for i in range(n)] for i in range(n)]
		solve(amount, ans)
		return ans

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		g = IntMatrix().Input(n, n)
		obj = Solution()
		res = obj.minCashFlow(n, g)
		IntMatrix().Print(res)


from typing import List

class Solution:

	def minCashFlow(self, n: int, g: List[List[int]]) -> List[List[int]]:

		def getMin(arr):
			minInd = 0
			for i in range(1, n):
				if arr[i] < arr[minInd]:
					minInd = i
			return minInd

		def getMax(arr):
			maxInd = 0
			for i in range(1, n):
				if arr[i] > arr[maxInd]:
					maxInd = i
			return maxInd

		def minCashFlowRec(amount):
			mxCredit = getMax(amount)
			mxDebit = getMin(amount)
			if amount[mxCredit] == 0 and amount[mxDebit] == 0:
				return 0
			mini = min(-amount[mxDebit], amount[mxCredit])
			amount[mxCredit] -= mini
			amount[mxDebit] += mini
			g[mxDebit][mxCredit] += mini
			minCashFlowRec(amount)
		net = [0] * n
		for i in range(n):
			for j in range(n):
				net[i] -= g[i][j]
				net[j] += g[i][j]
				g[i][j] = 0
		minCashFlowRec(net)
		return g

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		g = IntMatrix().Input(n, n)
		obj = Solution()
		res = obj.minCashFlow(n, g)
		IntMatrix().Print(res)