Given a directed graph, find out if a vertex j is reachable from another vertex i for all vertex pairs (i, j) in the given graph. Here reachable mean that there is a path from vertex i to j. The reach-ability matrix is called transitive closure of a graph. The directed graph is represented by adjacency list graph where there are N vertices.
Example 1:
Input: N = 4
graph = {{1, 1, 0, 1}, 
         {0, 1, 1, 0}, 
         {0, 0, 1, 1}, 
         {0, 0, 0, 1}}
Output: {{1, 1, 1, 1}, 
         {0, 1, 1, 1}, 
         {0, 0, 1, 1}, 
         {0, 0, 0, 1}}
Explaination: The output list shows the 
reachable indexes.
Your Task:
You do not need to read input or print anything. Your task is to complete the function transitiveClosure() which takes N and graph as input parameters and returns the transitive closure of the graph in form of 2d array.
Expected Time Complexity: O(N^{3})
Expected Auxiliary Space: O(N^{2})
Constraints:
1 ≤ N ≤ 100

Source: geeksforgeeks | Difficulty: EASY
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def transitiveClosure(self, N, graph):
        # code here

Solutions:
class Solution:

	def transitiveClosure(self, N, graph):
		g = [[] for _ in range(N)]
		for i in range(N):
			for j in range(N):
				if i != j and graph[i][j] == 1:
					g[i].append(j)

		def helper(node, prev, seen):
			if node in seen:
				return seen
			seen.add(node)
			for neig in g[node]:
				if neig != prev:
					helper(neig, node, seen)
			return seen
		output = [[0] * N for _ in range(N)]
		for i in range(N):
			x = helper(i, -1, set())
			while x:
				output[i][x.pop()] = 1
		return output


from itertools import product

class Solution:

	def transitiveClosure(self, N, graph):
		self.graph = graph
		self.N = N
		ans = []
		visited = [0 for i in range(N)]
		for i in range(N):
			self.helper(i, visited)
			ans.append(visited)
			visited = [0 for i in range(N)]
		return ans

	def helper(self, i, visited):
		visited[i] = 1
		for j in range(self.N):
			if j != i and self.graph[i][j] and (visited[j] == False):
				self.helper(j, visited)


from itertools import product

class Solution:

	def transitiveClosure(self, N, graph):
		for (k, i, j) in product(range(N), range(N), range(N)):
			graph[i][i] = 1
			if graph[i][k] and graph[k][j]:
				graph[i][j] = 1
		return graph


class Solution:

	def DFS(self, G, n, cMatrix, source, descendant):
		for neighbour in range(n):
			if G[descendant][neighbour] == 1:
				if cMatrix[source][neighbour] == 0:
					cMatrix[source][neighbour] = 1
					self.DFS(G, n, cMatrix, source, neighbour)

	def transitiveClosure(self, n, graph):
		cMatrix = [[0 for _ in range(n)] for _ in range(n)]
		for vertex in range(n):
			cMatrix[vertex][vertex] = 1
			self.DFS(graph, n, cMatrix, vertex, vertex)
		return cMatrix


class Solution:

	def transitiveClosure(self, N, graph):
		for k in range(N):
			for i in range(N):
				for j in range(N):
					if j == i:
						graph[i][j] = 1
					if graph[i][j] != 1:
						if graph[i][k] and graph[k][j] != 0:
							graph[i][j] = 1
		return graph


class Solution:

	def transitiveClosure(self, N, graph):
		for i in range(N):
			visited = [False for i in range(N)]
			s = []
			self.helper(visited, s, graph, i, N)
			for j in s:
				graph[i][j] = 1
		return graph

	def helper(self, visited, s, graph, node, N):
		if visited[node] != True:
			s.append(node)
			visited[node] = True
			for i in range(N):
				if graph[node][i] == 1:
					self.helper(visited, s, graph, i, N)


class Solution:

	def transitiveClosure(self, N, graph):
		adj = [i[:] for i in graph]
		for k in range(N):
			for i in range(N):
				for j in range(N):
					if i == j:
						adj[i][j] = 1
					else:
						adj[i][j] = adj[i][j] or (adj[i][k] and adj[k][j])
		return adj


class Solution:

	def transitiveClosure(self, N, graph):
		import copy
		reach = copy.deepcopy(graph)
		for i in range(N):
			reach[i][i] = 1
		for k in range(N):
			for i in range(N):
				for j in range(N):
					reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
		return reach


from queue import Queue

class Solution:

	def transitiveClosure(self, N, graph):
		tc = [[0 for _ in range(N)] for _ in range(N)]
		for i in range(N):
			tc[i][i] = 1
			q = Queue()
			q.put(i)
			vis = {i}
			while q.empty() != True:
				node = q.get()
				for j in range(N):
					if graph[node][j] == 1 and j not in vis:
						vis.add(j)
						tc[i][j] = 1
						q.put(j)
		return tc


class Solution:

	def transitiveClosure(self, N, graph):
		import copy
		reach = copy.deepcopy(graph)

		def bfs(cur, goal, vis):
			if cur is goal:
				return True
			flag = False
			for adj in range(N):
				if adj not in vis and graph[cur][adj]:
					vis.add(adj)
					flag = flag or bfs(adj, goal, vis)
			return flag
		for i in range(N):
			for j in range(N):
				vis = set()
				if bfs(i, j, vis):
					reach[i][j] = 1
		return reach


class Solution:

	def depthFirst(self, graph, source, dest, visited):
		if source == dest:
			return 1
		if source in visited:
			return 0
		visited.add(source)
		for neighbor in graph[source]:
			if Solution.depthFirst(self, graph, neighbor, dest, visited) == 1:
				return 1
		return 0

	def TurnToGraph(self, N, graph):
		adj = [[j for j in range(N) if graph[i][j] == 1] for i in range(N)]
		return adj

	def MakeRransitiveClosure(self, N, graph):
		visited = set()
		res = [[Solution.depthFirst(self, graph, i, j, visited=set()) for j in range(N)] for i in range(N)]
		return res

	def transitiveClosure(self, N, graph):
		myList = Solution.TurnToGraph(self, N, graph)
		res = Solution.MakeRransitiveClosure(self, N, myList)
		return res


class Solution:

	def transitiveClosure(self, N, graph):
		output = [[0 for i in range(N)] for i in range(N)]
		for i in range(N):
			self.DFSTransativeClosue(i, i, graph, output)
		return output

	def DFSTransativeClosue(self, s, v, graph, output):
		output[s][v] = 1
		for i in range(len(graph[v])):
			if graph[v][i] == 1 and output[s][i] == 0:
				self.DFSTransativeClosue(s, i, graph, output)


from collections import defaultdict

class Solution:

	def transitiveClosure(self, N, graph):
		d = defaultdict(list)
		for i in range(N):
			for j in range(N):
				if i != j:
					if graph[i][j] == 1:
						d[i].append(j)

		def dfs(n):
			if visit[n] == 0:
				visit[n] = 1
			for i in d[n]:
				if not visit[i]:
					dfs(i)
		mat = []
		for i in range(N):
			visit = [0] * N
			visit[i] = 1
			dfs(i)
			mat.append(visit)
		return mat


class Solution:

	def dfs(self, v, visited):
		visited[v] = 1
		for i in range(self.N):
			if i != v and self.graph[v][i] and (visited[i] == False):
				self.dfs(i, visited)

	def transitiveClosure(self, N, graph):
		self.graph = graph
		self.N = N
		res = []
		visited = [0] * N
		for i in range(N):
			self.dfs(i, visited)
			res.append(visited)
			visited = [0] * N
		return res


class Solution:

	def transitiveClosure(self, N, graph):
		reachable = [[0 for _ in range(N)] for _ in range(N)]
		for j in range(N):
			queue = [j]
			reachable[j][j] = 1
			for node in queue:
				for neighb in range(N):
					if graph[node][neighb] == 0:
						continue
					if not reachable[j][neighb]:
						reachable[j][neighb] = 1
						queue.append(neighb)
		return reachable

	def dfsNode(self, node, N, reachable, graph):
		traversal = [node]
		for neighb in range(N):
			if graph[node][neighb] == 0:
				continue
			if reachable[node][neighb] == 0:
				reachable[node][neighb] = 1
				if neighb != node:
					traversal += self.dfsNode(neighb, N, reachable, graph)
		for t in traversal:
			reachable[node][t] = 1
		return traversal


class Solution:

	def transitiveClosure(self, N, graph):
		INF = 4294967296
		for i in range(N):
			for j in range(N):
				graph[i][j] = INF if graph[i][j] == 0 else graph[i][j]

		def floydWarshall(V, graph):
			dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
			for k in range(V):
				for i in range(V):
					for j in range(V):
						dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
			return dist
		solution = floydWarshall(N, graph)
		for i in range(len(solution)):
			for j in range(len(solution)):
				solution[i][j] = int(solution[i][j] != INF) if i != j else 1
		return solution


def dfs(graph, visited, s, v, trans):
	visited[v] = True
	trans[s][v] = 1
	for i in range(len(graph)):
		if not visited[i] and graph[v][i]:
			dfs(graph, visited, s, i, trans)

class Solution:

	def transitiveClosure(self, N, graph):
		trans = [[0] * N for i in range(N)]
		for i in range(N):
			visited = [False] * N
			dfs(graph, visited, i, i, trans)
		return trans


class Solution:

	def transitiveClosure(self, n, graph):
		for i in range(n):
			ans = self.dfs(graph, n, i)
			for j in ans:
				graph[i][j] = 1
		return graph

	def dfs(self, graph, v, node):
		s = []
		adj = [[] for i in range(v)]
		visited = [False for i in range(v)]
		for i in range(v):
			for j in range(v):
				if graph[i][j] == 1:
					adj[i].append(j)
		self.helper(visited, node, s, adj)
		return s

	def helper(self, visited, node, s, adj):
		if visited[node] == False:
			s.append(node)
			visited[node] = True
			for i in adj[node]:
				self.helper(visited, i, s, adj)


class Solution:

	def transitiveClosure(self, N, graph):

		def dfs(node):
			if visited[node] == -1:
				visited[node] = 1
				for i in range(N):
					if node != i and graph[node][i] == 1:
						dfs(i)
		for node in range(N):
			visited = [-1] * N
			dfs(node)
			for j in range(N):
				if visited[j] == 1 and graph[node][j] == 0:
					graph[node][j] = 1
		return graph


from typing import List

class Solution:

	def depth_first_traversal(self, N: int, start_node: int, graph: List[List[int]], visited: List[bool], reachable: List[int]) -> None:
		visited[start_node] = True
		reachable.append(start_node)
		for neighbour in range(N):
			if graph[start_node][neighbour] and (not visited[neighbour]):
				self.depth_first_traversal(N, neighbour, graph, visited, reachable)

	def transitiveClosure(self, N, graph):
		closure = [[0 for j in range(N)] for i in range(N)]
		for node in range(N):
			reachable_nodes = []
			visited = [False for i in range(N)]
			self.depth_first_traversal(N, node, graph, visited, reachable_nodes)
			for reachable_node in reachable_nodes:
				closure[node][reachable_node] = 1
		return closure


from collections import deque

class Solution:

	def transitiveClosure(self, N, graph):
		adj = [[] for i in range(N)]
		for i in range(0, N):
			for j in range(0, N):
				if graph[i][j] == 1 and i != j:
					adj[i].append(j)
		final = []
		for i in range(0, N):
			ans = []
			self.bfs(i, adj, N, ans)
			final.append(ans)
		return final

	def bfs(self, src, adj, N, ans):
		visited = [False for i in range(N)]
		queue = deque([src])
		visited[src] = True
		while queue:
			node = queue.popleft()
			for neigh in adj[node]:
				if visited[neigh] == False:
					queue.append(neigh)
					visited[neigh] = True
		for i in range(0, N):
			if visited[i] == False:
				ans.append(0)
			else:
				ans.append(1)


class Solution:

	def transitiveClosure(self, n, graph):
		m = []
		for i in range(n):
			m.append([0] * n)
		for i in range(0, n):
			for j in range(0, n):
				flag = 0
				if i == j:
					m[i][j] = 1
				else:
					flag = DFS(i, j, graph, [], flag, n)
					m[i][j] = flag
		return m

def DFS(s, d, graph, visited, flag, n):
	visited.append(s)
	for i in range(0, n):
		if i not in visited:
			if graph[s][i] == 1:
				if i == d:
					flag = 1
					return flag
				else:
					flag = DFS(i, d, graph, visited, flag, n)
	return flag


class Solution:

	def DFS(self, N, graph, path: list, start, end):
		path[start][end] = 1
		for i in range(N):
			if start != i and end != i and (graph[end][i] == 1) and (path[start][i] == 0):
				self.DFS(N, graph, path, start, i)

	def transitiveClosure(self, N, graph):
		path = [[0 for i in range(N)] for j in range(N)]
		for i in range(N):
			self.DFS(N, graph, path, i, i)
		return path


from collections import defaultdict

class Solution:

	def __dfs(self, v, adj):
		self.visited[v] = True
		for u in adj[v]:
			if not self.visited[u]:
				self.__dfs(u, adj)

	def transitiveClosure(self, N, graph):
		adj = [[] for n in range(N)]
		for i in range(len(graph)):
			for j in range(len(graph[i])):
				if graph[i][j] == 1:
					adj[i].append(j)
		result = []
		V = N
		for v in range(V):
			self.visited = defaultdict(lambda : False)
			self.__dfs(v, adj)
			row = []
			for u in range(V):
				val = 0
				if self.visited[u]:
					val = 1
				row.append(val)
			result.append(row)
		return result


class Solution:

	def transitiveClosure(self, N, graph):

		def bfs(node):
			nonlocal set_seen
			set_seen.add(node)
			for (neighbor, reachable) in enumerate(graph[node]):
				if reachable and neighbor not in set_seen:
					bfs(neighbor)
		to_return = [[0] * N for i in range(N)]
		set_seen = set()
		for i in range(N):
			bfs(i)
			for reachable in set_seen:
				to_return[i][reachable] = 1
			set_seen = set()
		return to_return


class Solution:

	def transitiveClosure(self, n, graph):
		for i in range(n):
			graph[i][i] = 1
		for k in range(n):
			for i in range(n):
				for j in range(n):
					graph[i][j] = graph[i][j] or (graph[i][k] and graph[k][j])
		return graph


class Solution:

	def utill(self, v, visited):
		visited[v] = 1
		for i in range(self.N):
			if i != v and self.graph[v][i] and (visited[i] == False):
				self.utill(i, visited)

	def transitiveClosure(self, N, graph):
		self.graph = graph
		self.N = N
		ans = []
		visited = [0] * N
		for i in range(N):
			self.utill(i, visited)
			ans.append(visited)
			visited = [0] * N
		return ans


import numpy as np

class Solution:

	def transitiveClosure(self, N, graph):
		res = np.zeros((N, N))
		for i in range(0, N):
			for j in range(0, N):
				edge = graph[i]
				neighbour = edge[j]
				if i == j:
					res[i][j] = 1
				else:
					res[i][j] = neighbour
		for k in range(0, N):
			for i in range(0, N):
				for j in range(0, N):
					res[i][j] = res[i][j] or (res[i][k] and res[k][j])
		resGraph = []
		for i in range(0, N):
			resGraph.append([int(j) for j in res[i]])
		return resGraph


class Solution:

	def transitiveClosure(self, N, graph):
		for i in range(N):
			graph[i][i] = 1
		for k in range(len(graph)):
			for i in range(len(graph)):
				for j in range(len(graph)):
					if graph[i][k] == 0 or graph[k][j] == 0:
						continue
					if graph[i][j] > 0:
						graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
					else:
						graph[i][j] = graph[i][k] + graph[k][j]
		for i in range(len(graph)):
			for j in range(len(graph)):
				if graph[i][j] > 1:
					graph[i][j] = 1
		return graph


class Solution:

	def transitiveClosure(self, N, graph):
		transMat = [[graph[i][j] for j in range(N)] for i in range(N)]
		for i in range(N):
			transMat[i][i] = 1
		for mid in range(N):
			for i in range(N):
				for j in range(N):
					if not transMat[i][j] and transMat[i][mid] and transMat[mid][j]:
						transMat[i][j] = 1
		return transMat


class Solution:

	def transitiveClosure(self, N, A):
		for k in range(N):
			for i in range(N):
				for j in range(N):
					if i != j != k:
						if A[i][j] == 0:
							A[i][j] = float('inf')
						if A[k][j] == 0:
							A[k][j] = float('inf')
						if A[i][k] == 0:
							A[i][k] = float('inf')
					A[i][j] = min(A[i][j], A[i][k] + A[k][j])
		for i in range(len(A)):
			for j in range(len(A)):
				if A[i][j] == float('inf'):
					A[i][j] = 0
				else:
					A[i][j] = 1
				if i == j:
					A[i][j] = 1
		return A


class Solution:

	def dfs(self, node, visited):
		visited[node] = 1
		for neigh in range(self.N):
			if self.graph[node][neigh] and node != neigh and (not visited[neigh]):
				self.dfs(neigh, visited)

	def transitiveClosure(self, N, graph):
		self.N = N
		self.graph = graph
		ans = []
		for node in range(N):
			visited = [0] * N
			self.dfs(node, visited)
			ans.append(visited)
		return ans


class Solution:

	def transitiveClosure(self, N, graph):
		from collections import defaultdict
		dic = defaultdict(list)
		for i in range(N):
			for j in range(N):
				if graph[i][j] == 1:
					dic[i].append(j)
		ans = graph[:]

		def dfs(s, node, visited):
			if node in visited:
				return
			visited.add(node)
			ans[s][node] = 1
			for neg in dic[node]:
				dfs(s, neg, visited)
		for i in range(N):
			dfs(i, i, set())
		return ans


class Solution:

	def transitiveClosure(self, N, graph):
		a = [[] for i in range(N)]
		for i in range(N):
			for j in range(N):
				if i == j:
					graph[i][j] = 1
				if i != j and graph[i][j] == 1:
					a[i].append(j)
		for k in range(N):
			queue = [k]
			visited = [k]
			while queue:
				poped = queue.pop(0)
				for i in a[poped]:
					if i not in visited:
						queue.append(i)
						visited.append(i)
						graph[k][i] = 1
		return graph


class Solution:

	def transitiveClosure(self, N, graph):

		def dfs(i, traversed_list, d, graph):
			if i in d:
				return
			else:
				d.add(i)
				traversed_list.append(i)
				for (j, connected) in enumerate(graph[i]):
					if connected:
						dfs(j, traversed_list, d, graph)
		mat = graph.copy()
		for i in range(N):
			traversed_list = []
			d = set()
			dfs(i, traversed_list, d, graph)
			for j in traversed_list:
				mat[i][j] = 1
		return mat


class Solution:

	def dfs(self, graph, visited, i):
		visited[i] = 1
		for (idx, val) in enumerate(graph[i]):
			if val == 1 and idx != i and (visited[idx] != 1):
				self.dfs(graph, visited, idx)

	def transitiveClosure(self, N, graph):
		ans = []
		for i in range(N):
			visited = [0] * N
			self.dfs(graph, visited, i)
			ans.append(visited)
		return ans


class Solution:

	def transitiveClosure(self, N, graph):
		sol = graph
		for i in range(N):
			sol[i][i] = 1
			for j in range(N):
				sol[j][j] = 1
				for z in range(N):
					sol[z][z] = 1
					sol[j][z] = max(sol[j][z], min(sol[j][i], sol[i][z]))
					sol[z][j] = max(sol[z][j], min(sol[z][i], sol[i][j]))
		return sol


class Solution:

	def DFSUtil(self, N, visited, u, graph, adj):
		visited[u] = True
		adj.append(u)
		for v in range(N):
			if not visited[v] and graph[u][v] == 1:
				self.DFSUtil(N, visited, v, graph, adj)

	def DFS(self, N, graph):
		for i in range(N):
			adj = []
			visited = [False] * N
			if not visited[i]:
				self.DFSUtil(N, visited, i, graph, adj)
			for j in adj:
				graph[i][j] = 1
		return graph

	def transitiveClosure(self, N, graph):
		for i in range(N):
			graph[i][i] = 1
		return self.DFS(N, graph)


class Solution:

	def DFS(self, start, final, visited):
		visited[start] = True
		final[start] = 1
		for i in range(self.N):
			if i != start and self.G[start][i] == 1 and (visited[i] == False):
				self.DFS(i, final, visited)

	def transitiveClosure(self, N, graph):
		self.G = graph
		self.N = N
		Gra = []
		for src in range(0, self.N):
			visited = [False] * self.N
			final = [0] * self.N
			self.DFS(src, final, visited)
			Gra.append(final)
		return Gra


class Solution:

	def convertToList(self, adjMatrix):
		adjList = dict()
		for u in range(len(adjMatrix)):
			adjList[u] = []
			for v in range(len(adjMatrix[0])):
				if u != v and adjMatrix[u][v] == 1:
					adjList[u].append(v)
		return adjList

	def dfs(self, node, destNode, adjList, visited):
		visited.add(node)
		if node == destNode:
			return 1
		for nbr in adjList[node]:
			if nbr not in visited:
				result = self.dfs(nbr, destNode, adjList, visited)
				if result == 1:
					return 1
		return 0

	def transitiveClosure(self, N, graph):
		adjList = self.convertToList(graph)
		m = len(graph)
		n = len(graph[0])
		result = [[0] * n for _ in range(m)]
		for i in range(m):
			for j in range(n):
				if i == j:
					result[i][j] = 1
				else:
					visited = set()
					result[i][j] = self.dfs(i, j, adjList, visited)
		return result
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		graph = []
		for i in range(0, N):
			graph.append([int(j) for j in input().split()])
		ob = Solution()
		ans = ob.transitiveClosure(N, graph)
		for i in range(N):
			for j in range(N):
				print(ans[i][j], end=' ')
			print()


class Solution:

	def transitiveClosure(self, N, graph):
		for k in range(N):
			for i in range(N):
				for j in range(N):
					if i == j:
						graph[i][j] = 1
					else:
						graph[i][j] = graph[i][j] or (graph[i][k] and graph[k][j])
		return graph
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		graph = []
		for i in range(0, N):
			graph.append([int(j) for j in input().split()])
		ob = Solution()
		ans = ob.transitiveClosure(N, graph)
		for i in range(N):
			for j in range(N):
				print(ans[i][j], end=' ')
			print()


class Solution:

	def transitiveClosure(self, N, graph):

		def dfs(v, visited):
			visited[v] = 1
			for i in range(N):
				if i != v and graph[v][i] and (visited[i] == 0):
					dfs(i, visited)
		result = []
		visited = [0] * N
		for i in range(N):
			dfs(i, visited)
			result.append(visited)
			visited = [0] * N
		return result
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		graph = []
		for i in range(0, N):
			graph.append([int(j) for j in input().split()])
		ob = Solution()
		ans = ob.transitiveClosure(N, graph)
		for i in range(N):
			for j in range(N):
				print(ans[i][j], end=' ')
			print()


class Solution:

	def transitiveClosure(self, N, a):
		graph = []
		for i in a:
			b = []
			for j in range(len(i)):
				if i[j] == 1:
					b.append(j)
			graph.append(b)
		visited = [0] * N

		def bfs(k, to):
			q = [k]
			visited[k] = 1
			while q:
				t = q[0]
				for i in graph[t]:
					if not visited[i]:
						visited[i] = 1
						if i == to:
							return True
						q.append(i)
				q.pop(0)
			return False
		ans = [[0] * N for i in range(N)]
		for i in range(N):
			ans[i][i] = 1
		for i in range(N):
			for j in range(N):
				visited = [0] * N
				if bfs(i, j):
					ans[i][j] = 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		graph = []
		for i in range(0, N):
			graph.append([int(j) for j in input().split()])
		ob = Solution()
		ans = ob.transitiveClosure(N, graph)
		for i in range(N):
			for j in range(N):
				print(ans[i][j], end=' ')
			print()


class Solution:

	def transitiveClosure(self, N, graph):
		tc = [[0 for i in range(N)] for j in range(N)]
		for i in range(N):
			self.solve(i, i, graph, tc)
		return tc

	def solve(self, s, d, graph, tc):
		tc[s][d] = 1
		for i in range(len(graph[d])):
			if graph[d][i] == 1:
				if tc[s][i] != 1:
					if s != i:
						self.solve(s, i, graph, tc)
					else:
						tc[s][i] = 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		graph = []
		for i in range(0, N):
			graph.append([int(j) for j in input().split()])
		ob = Solution()
		ans = ob.transitiveClosure(N, graph)
		for i in range(N):
			for j in range(N):
				print(ans[i][j], end=' ')
			print()


class Solution:

	def dfs(self, i, j, ans):
		stack = [i]
		visited = set()
		while stack:
			c = stack.pop()
			ans[i][c] = 1
			visited.add(c)
			for n in range(N):
				if graph[c][n] == 1 and n not in visited:
					stack.append(n)
					visited.add(n)

	def transitiveClosure(self, N, graph):
		ans = [[0 for i in range(N)] for j in range(N)]
		for i in range(N):
			self.dfs(i, i, ans)
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		graph = []
		for i in range(0, N):
			graph.append([int(j) for j in input().split()])
		ob = Solution()
		ans = ob.transitiveClosure(N, graph)
		for i in range(N):
			for j in range(N):
				print(ans[i][j], end=' ')
			print()


class Solution:

	def transitiveClosure(self, N, graph):
		res = []
		for i in range(N):
			vertex_to_DFS = graph[i]
			stack = []
			visited = [0 for x in range(N)]
			for j in range(N):
				if i == j:
					visited[j] = 1
				elif vertex_to_DFS[j] == 1 and visited[j] == 0:
					stack.insert(0, j)
					visited[j] = 1
					while stack:
						v = stack.pop(0)
						for k in range(N):
							if not visited[k] and graph[v][k] == 1:
								stack.insert(0, k)
								visited[k] = 1
			res.append(visited)
		return res


class Solution:

	def transitiveClosure(self, N, graph):
		output = [[None for i in range(N)] for j in range(N)]
		for i in range(N):
			for j in range(N):
				if graph[i][j] == 1:
					output[i][j] = 1
				elif graph[i][j] == 0:
					if i == j:
						output[i][j] = 1
					elif self.isthere(graph, i, j, N, []):
						output[i][j] = 1
					else:
						output[i][j] = 0
		return output

	def isthere(self, graph, src, des, N, recstack):
		if graph[src][des] == 1:
			return True
		else:
			recstack.append(src)
			for i in range(N):
				if graph[src][i] == 1 and src != i and (i not in recstack):
					if self.isthere(graph, i, des, N, recstack) == True:
						return True
		return False


from queue import Queue

class Solution:

	def transitiveClosure(self, N, graph):
		for i in range(N):
			graph[i][i] = 1
			q = Queue(maxsize=N)
			visited = [None for i in range(N)]
			q.put(i)
			while q.qsize():
				k = q.get()
				graph[i][k] = 1
				for y in range(N):
					if graph[k][y] == 1 and (not visited[y]):
						visited[y] = 1
						q.put(y)
				visited[k] = True
		return graph


from collections import defaultdict

class Solution:

	def DFSUtill2(self, s, v, graph, N):
		if s == v:
			self.ans[s][v] = 1
		elif graph[s][v]:
			self.ans[s][v] = 1
		else:
			for i in range(N):
				if graph[s][i]:
					if graph[i][v]:
						self.ans[s][v] = 1

	def transitiveClosure(self, N, graph):
		for i in range(N):
			graph[i][i] = 1
		for i in range(N):
			for j in range(N):
				for k in range(N):
					if graph[j][i] and graph[i][k]:
						graph[j][k] = 1
		return graph