Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

ChefsLand can be viewed as a graph consisting of N cities and bidirectional roads. Each pair of cities is directly connected by a road. Recently, Chef came up with following game to make the Number Theory course more interesting for students in country schools.

At the beginning of each lesson, Chef draws ChefsLand as a graph with N vertices corresponding to cities and N(N-1)/2 edges corresponding to roads between them. Then he labels the cities; each city is given a distinct label between 1 and N (inclusive). Next, he labels each edge — the label of the edge between vertices u and v is the common divisor count of lbl_{u} and lbl_{v} (the number of positive integers which divide both lbl_{u} and lbl_{v}), where lbl_{u} and lbl_{v} denote the labels of vertices u and v respectively.

Now, Chef erases the vertex labels, retaining only edge labels in the graph. You, as the number theory student, should find some assignment of labels to vertices which produces a graph with the given edge labels.

------ Input ------ 

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of vertices in the graph.
The following N lines describe the labels of edges. For each valid i, the i-th of these lines contains N space-separated integers M_{i1}, M_{i2}, ..., M_{iN}; for each valid j ≠ i, M_{ij} represents the label of the edge connecting vertices i and j.

------ Output ------ 

For each test case, print N lines. For each valid i, the i-th of these lines should contain a single integer — the label of the i-th vertex.

If there are multiple solutions, you may output any one.

------ Constraints ------ 

$1 ≤ N ≤ 1000$
$for each valid i, M_{ii} = 0$
$it's guaranteed that for the given edge labels, at least one possible assignment of labels to vertices exists$

------ Subtasks ------ 

Subtask #1 (15 points): sum of N for all test cases ≤ 10

Subtask #2 (85 points): sum of N for all test cases ≤ 1000

------ Example ------ 

Input:

1
4
0 1 1 1
1 0 1 1
1 1 0 2
1 1 2 0

Output:

3
1
2
4

Difficulty: VERY_HARD
Tags: Graph algorithms

Constructive algorithms

String algorithms

Number theory

Mathematics

Starter code:

Solutions:
def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
f = [0 for i in range(1001)]
for i in range(1, 1001):
	for j in range(1, i + 1):
		if i % j == 0:
			f[i] += 1
t = int(input())
for i in range(t):
	n = int(input())
	s = [[] for i in range(n)]
	m = [[] for i in range(n)]
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if i == j:
				m[i - 1].append(0)
			else:
				m[i - 1].append(f[gcd(i, j)])
		s[i - 1] = sorted(m[i - 1])
	r = [[] for i in range(n)]
	p = [[] for i in range(n)]
	for i in range(0, n):
		r[i] = list(map(int, input().split()))
		p[i] = sorted(r[i])
	ans = []
	vis = [0 for i in range(n)]
	for i in range(0, n):
		for j in range(n):
			if vis[j] == 0 and p[i] == s[j]:
				c = 1
				for k in range(i):
					if m[j][ans[k]] != r[i][k]:
						c = 0
						break
				if c:
					ans.append(j)
					vis[j] = 1
					break
	for i in ans:
		print(i + 1)


import math
from collections import Counter
list4 = []

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def countDivisors(e):
	cnt = 0
	for k in range(1, int(math.sqrt(e)) + 1):
		if e % k == 0:
			if e / k == k:
				cnt = cnt + 1
			else:
				cnt = cnt + 2
	return cnt
for i in range(1, 1001):
	list3 = []
	for j in range(1, 1001):
		if i == j:
			list3.append(0)
		else:
			e = gcd(i, j)
			d = countDivisors(e)
			list3.append(d)
	list4.append(list3)
for _ in range(int(input())):
	n = int(input())
	(list1, list5, list6, list10, list12) = ([], [], [], [], [])
	(list8, list9, list13, list7) = ([0] * n, [0] * n, [0] * n, [0] * n)
	for i in range(n):
		list2 = list(map(int, input().split()))
		list1.append(list2)
		d = Counter(list2)
		list6.append(d)
	for i in range(n):
		e = Counter(list4[i][0:n])
		list5.append(e)
	for i in range(n):
		list11 = []
		if list9[i] != 1:
			for j in range(n):
				if list5[i] == list5[j] and i != j and (list9[j] != 1):
					list11.append(j + 1)
					list9[j] = 1
			list11.append(i + 1)
			list10.append(list11)
	for i in range(len(list10)):
		if len(list10[i]) == 1:
			list13[list10[i][0] - 1] = 1
	list21 = [0] * n
	count = 0
	for i in range(n):
		for j in range(n):
			if list6[i] == list5[j] and list13[j] == 1:
				if list7[j] != 1:
					count += 1
					list7[i] = j + 1
					list21[j] = 1
					break
			if list6[i] == list5[j]:
				if j + 1 in list10[0]:
					if list7[j] != 1:
						count += 1
						list10[0].remove(j + 1)
						list7[i] = j + 1
						list21[j] = 1
						break
	for i in range(n):
		if list7[i] == 0:
			for j in range(n):
				c = 0
				if list6[i] == list5[j]:
					if list21[j] == 0:
						if count > 0:
							for k in range(n):
								if list7[k] != 0:
									f = gcd(list7[k], j + 1)
									g = countDivisors(f)
									if g != list1[k][i]:
										c = 1
										break
						if c == 0:
							list7[i] = j + 1
							count += 1
							list21[j] = 1
							break
						else:
							continue
	for k in list7:
		print(k)


import math
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
prohibitedprimes = [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [7], [], [], [], [], [], [10], [], [], [], [12], [], [13], [], [], [], [], [], [], [], [11], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [16], [], [], [], [], [], [18], [], [], [], [], [], [], [], [], [21], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [19], [19], [19], [], [], [20], [20], [20], [20], [], [], [], [], [], [], [22], [22], [], [], [], [23], [23], [], [], [23], [], [], [], [], [], [25], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [30], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [37, 27], [27], [27], [27], [27], [27], [27], [], [], [28], [28], [28], [28], [28], [], [40, 29], [29], [29], [29], [29], [29], [30], [30], [30], [30], [30], [30], [30], [], [], [], [31], [], [], [], [44, 32], [32], [32], [32], [32], [32], [32], [33], [33], [33], [33], [33], [33], [33], [34], [34], [34], [34], [], [], [], [35], [35], [35], [35], [35], [35], [35], [], [36], [36], [], [], [], [], [37], [37], [37], [37], [37], [], [], [38], [38], [38], [38], [38], [38], [], [39], [39], [], [], [], [], [], [40], [40], [40], [40], [40], [40], [40], [41], [41], [], [], [], [], [], [42], [42], [42], [], [], [], [], [43], [43], [43], [43], [43], [], [], [], [], [], [], [], [], [], [45], [45], [45], [45], [], [], [], [46], [], [], [], [], [], [], [47], [], [], [], [], [], [], [48], [48], [48], [48], [], [], [48], [], [], [], [], [], [], [], [50], [50], [], [], [], [], [], [], [], [], [], [], [], [51], [], [], [], [], [], [], [], [53], [53], [53], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [41], [41], [41], [41], [41], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [43], [43], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [45], [45], [45], [45], [45], [45], [45], [45], [45], [45], [45], [], [], [], [], [46], [46], [46], [46], [46], [46], [46], [], [], [], [], [], [47], [47], [47], [47], [47], [47], [48], [48], [48], [48], [48], [48], [48], [48], [48], [48], [48], [], [], [], [], [], [49], [49], [49], [49], [49], [49], [50], [50], [50], [50], [50], [50], [50], [50], [50], [50], [50], [51], [51], [51], [51], [51], [51], [51], [51], [51], [51], [51], [], [], [], [], [], [], [52], [52], [], [], [], [53], [53], [53], [53], [53], [53], [53], [53], [53], [53], [53], [], [54], [54], [54], [54], [54], [54], [54], [54], [54], [54], [], [], [], [], [55], [55], [55], [], [], [], [], [56], [56], [56], [56], [56], [56], [56], [56], [56], [56], [56], [], [], [57], [57], [57], [57], [57], [57], [57], [57], [57], [58], [58], [58], [58], [58], [58], [58], [58], [], [], [], [59], [59], [59], [59], [59], [59], [59], [59], [59], [59], [59], [], [], [], [60], [60], [60], [60], [51], [51], [51], [51], [61, 51], [61, 51], [61, 51], [61, 51], [61, 51], [61], [61], [61], [61], [], [], [62], [62], [62], [62], [62], [62], [62], [62], [62], [62], [62], [], [], [], [63, 53], [53], [53], [53], [53], [53], [], [], [64], [64], [64], [64], [64], [64], [64], [64], [64], [64, 54], [64, 54], [65, 55], [65, 55], [65, 55], [65, 55], [65, 55], [65, 55], [65, 55], [65], [65], [65], [55], [66, 55], [66, 55], [66, 56], [66, 56], [66, 56], [56], [56], [56], [56], [56], [56], [67, 56], [67, 56], [67, 56], [67, 56], [67], [67], [67], [67], [67], [67], [67], [68], [68], [68], [68], [68], [68], [58], [58], [58], [58], [58], [69, 58], [69, 58], [69, 58], [69, 58], [69, 58], [69, 58], [58], [58], [59], [59], [59], [70, 59], [70, 59], [70, 59], [70, 59], [70, 59], [70, 59], [70, 59], [70], [70], [70, 59], [70], [], [71], [60], [60], [60], [60], [60], [60], [60], [60], [60], [72, 60], [72, 61], [72, 61], [72, 61], [72, 61], [72, 61], [72], [], [], [], [], [73], [73], [73, 61], [73, 62], [73, 62], [73, 62], [73, 62], [73, 62], [73, 62], [62], [62], [74, 62], [74, 62], [74, 62], [74, 62], [74, 62], [], [], [], [], [], [], [75], [75], [75], [75, 63], [75, 63], [75, 63], [75, 63], [75, 64], [64], [64], [64], [76], [76], [76], [76], [76], [76, 64], [76, 64], [76, 64], [76, 64], [65], [65], [77, 65], [77, 65], [77, 65], [77, 65], [77, 65], [77, 65], [77, 65], [65], [65], [65], [65], [78], [78], [78], [78], [78], [78], [78], [78], [78], [], [78], [79], [79, 66], [79, 67], [79, 67], [79, 67], [79, 67], [79, 67], [79, 67], [79, 67], [79, 67], [79, 67], [80, 67], [80, 67], [80, 67], [80, 67], [80, 68], [80, 68], [80, 68], [80, 68], [80], [80], [80], [81], [81], [81], [81], [81], [81], [81], [81], [81, 69], [81, 69], [81, 69], [82, 69], [82, 69], [82, 69], [82, 69], [82, 69], [82, 69], [82, 69], [82, 69], [82, 70], [82, 70], [82], [83], [83], [83], [83], [83], [70], [70], [70], [70], [70], [83, 71], [84, 71], [84], [84], [84], [71], [71], [71], [71], [71], [71], [71], [85, 71], [], [], [85], [85], [85], [85], [85], [85, 72], [85, 72], [85, 72], [86, 72], [86, 72], [86, 72], [86, 73], [86], [86], [86], [86], [86, 73], [86, 73], [86, 73], [87, 73], [87, 73], [87, 73], [87, 73], [87, 73], [87], [87], [87], [87], [87, 74], [87, 74], [88, 74], [88, 74], [88, 74], [88, 74], [88, 74], [88, 74], [88, 74], [88], [88], [88], [88], [89], [89], [89], [89], [89], [89], [89], [75], [75], [89], [89, 76], [76], [76], [76], [76], [76], [76], [76], [76], [76], [76], [76]]
solutionofprimes = [{}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {7: [3, 5]}, {}, {}, {}, {}, {}, {10: [3, 5]}, {}, {}, {}, {12: [3, 5]}, {}, {13: [3, 5]}, {}, {}, {}, {}, {}, {}, {}, {11: [5, 7]}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {16: [5, 7]}, {}, {}, {}, {}, {}, {18: [5, 7]}, {}, {}, {}, {}, {}, {}, {}, {}, {21: [5, 7]}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {19: [7, 13]}, {19: [7, 13]}, {19: [7, 13]}, {}, {}, {20: [7, 13]}, {20: [7, 13]}, {20: [7, 13]}, {20: [7, 13]}, {}, {}, {}, {}, {}, {}, {22: [7, 13]}, {22: [7, 13]}, {}, {}, {}, {23: [7, 13]}, {23: [7, 13]}, {}, {}, {23: [7, 17]}, {}, {}, {}, {}, {}, {25: [7, 13]}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {30: [7, 17]}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {37: [7, 17], 27: [11, 17]}, {27: [11, 17]}, {27: [11, 17]}, {27: [11, 17]}, {27: [11, 17]}, {27: [11, 17]}, {27: [11, 17]}, {}, {}, {28: [11, 17]}, {28: [11, 17]}, {28: [11, 17]}, {28: [11, 17]}, {28: [11, 17]}, {}, {40: [7, 17], 29: [11, 17]}, {29: [11, 17]}, {29: [11, 17]}, {29: [11, 17]}, {29: [11, 17]}, {29: [11, 19]}, {30: [11, 17]}, {30: [11, 17]}, {30: [11, 17]}, {30: [11, 17]}, {30: [11, 17]}, {30: [11, 17]}, {30: [11, 17]}, {}, {}, {}, {31: [11, 17]}, {}, {}, {}, {44: [7, 17], 32: [11, 17]}, {32: [11, 17]}, {32: [11, 17]}, {32: [11, 17]}, {32: [11, 17]}, {32: [11, 17]}, {32: [11, 17]}, {33: [11, 17]}, {33: [11, 17]}, {33: [11, 17]}, {33: [11, 17]}, {33: [11, 17]}, {33: [11, 17]}, {33: [11, 17]}, {34: [11, 17]}, {34: [11, 17]}, {34: [11, 17]}, {34: [11, 17]}, {}, {}, {}, {35: [11, 17]}, {35: [11, 17]}, {35: [11, 17]}, {35: [11, 17]}, {35: [11, 17]}, {35: [11, 17]}, {35: [11, 17]}, {}, {36: [11, 17]}, {36: [11, 17]}, {}, {}, {}, {}, {37: [11, 17]}, {37: [11, 17]}, {37: [11, 17]}, {37: [11, 17]}, {37: [11, 17]}, {}, {}, {38: [11, 17]}, {38: [11, 17]}, {38: [11, 17]}, {38: [11, 17]}, {38: [11, 17]}, {38: [11, 17]}, {}, {39: [11, 17]}, {39: [11, 17]}, {}, {}, {}, {}, {}, {40: [11, 17]}, {40: [11, 17]}, {40: [11, 17]}, {40: [11, 17]}, {40: [11, 17]}, {40: [11, 17]}, {40: [11, 19]}, {41: [11, 17]}, {41: [11, 17]}, {}, {}, {}, {}, {}, {42: [11, 17]}, {42: [11, 17]}, {42: [11, 17]}, {}, {}, {}, {}, {43: [11, 17]}, {43: [11, 17]}, {43: [11, 17]}, {43: [11, 17]}, {43: [11, 17]}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {45: [11, 17]}, {45: [11, 17]}, {45: [11, 17]}, {45: [11, 17]}, {}, {}, {}, {46: [11, 17]}, {}, {}, {}, {}, {}, {}, {47: [11, 17]}, {}, {}, {}, {}, {}, {}, {48: [11, 17]}, {48: [11, 17]}, {48: [11, 17]}, {48: [11, 17]}, {}, {}, {48: [11, 19]}, {}, {}, {}, {}, {}, {}, {}, {50: [11, 17]}, {50: [11, 17]}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {51: [11, 19]}, {}, {}, {}, {}, {}, {}, {}, {53: [11, 17]}, {53: [11, 17]}, {53: [11, 17]}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {41: [19, 23]}, {41: [19, 23]}, {41: [19, 23]}, {41: [19, 23]}, {41: [19, 23]}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {43: [19, 23]}, {43: [19, 23]}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {45: [17, 29]}, {45: [17, 29]}, {45: [17, 29]}, {45: [17, 29]}, {45: [17, 29]}, {45: [17, 29]}, {45: [17, 29]}, {45: [17, 29]}, {45: [17, 29]}, {45: [17, 29]}, {45: [17, 29]}, {}, {}, {}, {}, {46: [17, 29]}, {46: [17, 29]}, {46: [17, 29]}, {46: [17, 29]}, {46: [17, 29]}, {46: [17, 29]}, {46: [17, 29]}, {}, {}, {}, {}, {}, {47: [17, 29]}, {47: [17, 29]}, {47: [17, 29]}, {47: [17, 29]}, {47: [17, 29]}, {47: [17, 31]}, {48: [17, 29, 19, 23]}, {48: [17, 29]}, {48: [17, 29]}, {48: [17, 29]}, {48: [17, 29]}, {48: [17, 29]}, {48: [17, 29]}, {48: [17, 29]}, {48: [17, 29]}, {48: [17, 29]}, {48: [17, 29]}, {}, {}, {}, {}, {}, {49: [17, 29]}, {49: [17, 29]}, {49: [17, 29]}, {49: [17, 29]}, {49: [17, 29]}, {49: [17, 29]}, {50: [19, 23]}, {50: [17, 29]}, {50: [17, 29]}, {50: [17, 29]}, {50: [17, 29]}, {50: [17, 29]}, {50: [17, 29]}, {50: [17, 29]}, {50: [17, 29]}, {50: [17, 29]}, {50: [17, 29]}, {51: [17, 29]}, {51: [17, 29]}, {51: [17, 29]}, {51: [17, 29]}, {51: [17, 29]}, {51: [17, 29]}, {51: [17, 29]}, {51: [17, 29]}, {51: [17, 29]}, {51: [17, 29]}, {51: [17, 29]}, {}, {}, {}, {}, {}, {}, {52: [17, 29]}, {52: [17, 29]}, {}, {}, {}, {53: [17, 29]}, {53: [17, 29]}, {53: [17, 29]}, {53: [17, 29]}, {53: [17, 29]}, {53: [17, 29]}, {53: [17, 29]}, {53: [17, 29]}, {53: [17, 29]}, {53: [17, 29]}, {53: [17, 29]}, {}, {54: [17, 29]}, {54: [17, 29]}, {54: [17, 29]}, {54: [17, 29]}, {54: [17, 29]}, {54: [17, 29]}, {54: [17, 29]}, {54: [17, 29]}, {54: [17, 29]}, {54: [17, 29]}, {}, {}, {}, {}, {55: [17, 29]}, {55: [17, 29]}, {55: [17, 29]}, {}, {}, {}, {}, {56: [17, 29]}, {56: [17, 29]}, {56: [17, 29]}, {56: [17, 29]}, {56: [17, 29]}, {56: [17, 29]}, {56: [17, 29]}, {56: [17, 29]}, {56: [17, 29]}, {56: [17, 29]}, {56: [17, 29]}, {}, {}, {57: [17, 29]}, {57: [17, 29]}, {57: [17, 29]}, {57: [17, 29]}, {57: [17, 29]}, {57: [17, 29]}, {57: [17, 29]}, {57: [17, 29]}, {57: [17, 29]}, {58: [17, 29]}, {58: [17, 29]}, {58: [17, 29]}, {58: [17, 29]}, {58: [17, 29]}, {58: [17, 29]}, {58: [17, 29]}, {58: [17, 29]}, {}, {}, {}, {59: [17, 29]}, {59: [17, 29]}, {59: [17, 29]}, {59: [17, 29]}, {59: [17, 29]}, {59: [17, 29]}, {59: [17, 29]}, {59: [17, 29]}, {59: [17, 29]}, {59: [17, 29]}, {59: [17, 29]}, {}, {}, {}, {60: [17, 29]}, {60: [17, 29]}, {60: [17, 29]}, {60: [17, 29]}, {51: [23, 29]}, {51: [23, 29]}, {51: [23, 29]}, {51: [23, 29]}, {61: [17, 29], 51: [23, 29]}, {61: [17, 29], 51: [23, 29]}, {61: [17, 29], 51: [23, 29]}, {61: [17, 29], 51: [23, 29]}, {61: [17, 29], 51: [23, 29]}, {61: [17, 29]}, {61: [17, 29]}, {61: [17, 29]}, {61: [17, 29]}, {}, {}, {62: [17, 29]}, {62: [17, 29]}, {62: [17, 29]}, {62: [17, 29]}, {62: [17, 29]}, {62: [17, 29]}, {62: [17, 29]}, {62: [17, 29]}, {62: [17, 29]}, {62: [17, 29]}, {62: [17, 29]}, {}, {}, {}, {63: [17, 29], 53: [23, 29]}, {53: [23, 29]}, {53: [23, 29]}, {53: [23, 29]}, {53: [23, 29]}, {53: [23, 29]}, {}, {}, {64: [17, 29]}, {64: [17, 29]}, {64: [17, 29]}, {64: [17, 29]}, {64: [17, 29]}, {64: [17, 29]}, {64: [17, 29]}, {64: [17, 29]}, {64: [17, 29]}, {64: [17, 29], 54: [23, 29]}, {64: [17, 31], 54: [23, 29]}, {65: [17, 29], 55: [19, 37]}, {65: [17, 29], 55: [19, 37]}, {65: [17, 29], 55: [19, 37]}, {65: [17, 29], 55: [19, 37]}, {65: [17, 29], 55: [19, 37]}, {65: [17, 29], 55: [19, 37]}, {65: [17, 29], 55: [19, 37]}, {65: [17, 29]}, {65: [17, 29]}, {65: [17, 29]}, {55: [23, 29]}, {66: [17, 29], 55: [23, 29]}, {66: [17, 29], 55: [23, 29]}, {66: [17, 29], 56: [19, 37]}, {66: [17, 29], 56: [19, 37]}, {66: [17, 29], 56: [19, 37]}, {56: [19, 37]}, {56: [19, 37]}, {56: [19, 37]}, {56: [19, 37]}, {56: [19, 37]}, {56: [19, 37, 23, 29]}, {67: [17, 29], 56: [19, 37, 23, 29]}, {67: [17, 29], 56: [19, 37, 23, 29]}, {67: [17, 29], 56: [19, 37, 23, 29]}, {67: [17, 29], 56: [23, 29]}, {67: [17, 29]}, {67: [17, 29]}, {67: [17, 29]}, {67: [17, 29]}, {67: [17, 29]}, {67: [17, 29]}, {67: [17, 29]}, {68: [17, 29]}, {68: [17, 29]}, {68: [17, 29]}, {68: [17, 29]}, {68: [17, 29]}, {68: [17, 29]}, {58: [19, 37]}, {58: [19, 37]}, {58: [19, 37]}, {58: [19, 37]}, {58: [19, 37]}, {69: [17, 29], 58: [19, 37, 23, 29]}, {69: [17, 29], 58: [23, 29]}, {69: [17, 29], 58: [23, 29]}, {69: [17, 29], 58: [23, 29]}, {69: [17, 29], 58: [23, 29]}, {69: [17, 29], 58: [23, 29]}, {58: [23, 29]}, {58: [23, 29]}, {59: [19, 37]}, {59: [19, 37]}, {59: [19, 37]}, {70: [17, 29], 59: [19, 37]}, {70: [17, 29], 59: [19, 37]}, {70: [17, 29], 59: [19, 37]}, {70: [17, 29], 59: [19, 37]}, {70: [17, 29], 59: [19, 37]}, {70: [17, 29], 59: [19, 37]}, {70: [17, 29], 59: [19, 37]}, {70: [17, 29]}, {70: [17, 29]}, {70: [17, 29], 59: [19, 41]}, {70: [17, 29]}, {}, {71: [17, 29]}, {60: [23, 29]}, {60: [23, 29]}, {60: [23, 29]}, {60: [23, 29]}, {60: [23, 29]}, {60: [23, 29]}, {60: [23, 29]}, {60: [23, 29]}, {60: [23, 29]}, {72: [13, 59, 17, 29], 60: [23, 29]}, {72: [17, 29], 61: [19, 37]}, {72: [17, 29], 61: [19, 37]}, {72: [17, 29], 61: [19, 37]}, {72: [17, 29], 61: [19, 37]}, {72: [17, 29], 61: [19, 37]}, {72: [17, 29]}, {}, {}, {}, {}, {73: [13, 59, 61, 17, 29]}, {73: [13, 59, 61, 17, 29]}, {73: [13, 59, 61, 17, 29], 61: [23, 29]}, {73: [17, 29], 62: [19, 37]}, {73: [17, 29], 62: [19, 37]}, {73: [17, 29], 62: [19, 37]}, {73: [17, 29], 62: [19, 37]}, {73: [17, 29], 62: [19, 37]}, {73: [17, 29], 62: [19, 37]}, {62: [19, 37, 23, 29]}, {62: [19, 37, 23, 29]}, {74: [13, 59, 61, 17, 29], 62: [23, 29]}, {74: [13, 59, 61, 17, 29], 62: [23, 29]}, {74: [13, 59, 61], 62: [23, 29]}, {74: [13, 59, 61], 62: [23, 29]}, {74: [13, 59, 61], 62: [23, 29]}, {}, {}, {}, {}, {}, {}, {75: [13, 59, 61, 17, 29]}, {75: [13, 61, 17, 29]}, {75: [13, 61, 17, 29]}, {75: [13, 61, 17, 29], 63: [23, 29]}, {75: [13, 61, 17, 29], 63: [23, 29]}, {75: [13, 61, 17, 29], 63: [23, 29]}, {75: [13, 61, 17, 29], 63: [23, 29]}, {75: [17, 29], 64: [17, 47, 19, 37]}, {64: [19, 37]}, {64: [19, 37]}, {64: [19, 37]}, {76: [13, 61, 17, 29]}, {76: [13, 61, 17, 29]}, {76: [13, 61, 17, 29]}, {76: [13, 61, 17, 29]}, {76: [13, 61, 17, 29]}, {76: [13, 61], 64: [23, 29]}, {76: [13, 61], 64: [23, 29]}, {76: [13, 61], 64: [23, 29]}, {76: [13, 61], 64: [23, 29]}, {65: [17, 47, 19, 37]}, {65: [19, 37]}, {77: [13, 61, 17, 29], 65: [19, 37]}, {77: [13, 61, 17, 29], 65: [19, 37]}, {77: [13, 61, 17, 29], 65: [19, 37]}, {77: [13, 61], 65: [19, 37]}, {77: [13, 61], 65: [23, 29]}, {77: [13, 61], 65: [23, 29]}, {77: [13, 61], 65: [23, 29]}, {65: [23, 29]}, {65: [23, 29]}, {65: [23, 29]}, {65: [23, 29]}, {78: [17, 29]}, {78: [17, 29]}, {78: [17, 29]}, {78: [17, 29]}, {78: [17, 29]}, {78: [17, 29]}, {78: [17, 29]}, {78: [17, 29]}, {78: [17, 29]}, {}, {78: [17, 31]}, {79: [13, 59, 61, 17, 29]}, {79: [13, 59, 61], 66: [23, 29]}, {79: [13, 67], 67: [19, 37]}, {79: [13, 67], 67: [19, 37]}, {79: [13, 67], 67: [19, 37]}, {79: [13, 67], 67: [23, 29]}, {79: [13, 67], 67: [23, 29]}, {79: [13, 67], 67: [23, 29]}, {79: [13, 67], 67: [23, 29]}, {79: [13, 67], 67: [23, 29]}, {79: [13, 67], 67: [23, 29]}, {80: [13, 59, 61, 17, 29], 67: [23, 29]}, {80: [13, 59, 61, 17, 29], 67: [23, 29]}, {80: [13, 59, 61, 17, 29], 67: [23, 29]}, {80: [13, 59, 61, 17, 29], 67: [23, 29]}, {80: [13, 67], 68: [19, 37]}, {80: [13, 67], 68: [19, 37]}, {80: [13, 67], 68: [19, 37]}, {80: [13, 67], 68: [19, 37]}, {80: [13, 67]}, {80: [13, 67]}, {80: [13, 67]}, {81: [13, 61, 17, 29]}, {81: [13, 61, 17, 29]}, {81: [13, 61, 17, 29]}, {81: [13, 61, 17, 29]}, {81: [13, 61, 17, 29]}, {81: [13, 61, 17, 29]}, {81: [13, 67, 17, 29]}, {81: [13, 67, 17, 29]}, {81: [13, 67], 69: [23, 29]}, {81: [13, 67], 69: [23, 29]}, {81: [13, 67, 17, 31], 69: [17, 53, 23, 29]}, {82: [13, 61], 69: [17, 53, 23, 29]}, {82: [13, 61], 69: [17, 53, 23, 29]}, {82: [13, 61], 69: [17, 53, 23, 29]}, {82: [13, 61], 69: [17, 53, 23, 29]}, {82: [13, 61], 69: [17, 53, 23, 29]}, {82: [13, 61], 69: [17, 53, 23, 29]}, {82: [13, 61], 69: [17, 53, 23, 29]}, {82: [13, 61], 69: [17, 53, 23, 29]}, {82: [13, 67], 70: [19, 37]}, {82: [13, 67], 70: [19, 37]}, {82: [13, 67]}, {83: [13, 61, 17, 29]}, {83: [13, 61, 17, 29]}, {83: [17, 29]}, {83: [17, 29]}, {83: [17, 29]}, {70: [17, 53]}, {70: [17, 53]}, {70: [17, 53, 23, 29]}, {70: [17, 53, 23, 29]}, {70: [17, 53, 23, 29]}, {83: [13, 67, 71], 71: [19, 37]}, {84: [17, 29], 71: [19, 37]}, {84: [17, 29]}, {84: [17, 29]}, {84: [17, 29]}, {71: [23, 29]}, {71: [23, 29]}, {71: [23, 29]}, {71: [23, 29]}, {71: [23, 29]}, {71: [23, 29]}, {71: [23, 29]}, {85: [13, 59, 61], 71: [17, 53, 23, 29]}, {}, {}, {85: [13, 67]}, {85: [13, 67]}, {85: [13, 67]}, {85: [13, 67]}, {85: [13, 67]}, {85: [13, 67], 72: [23, 29]}, {85: [13, 67], 72: [23, 29]}, {85: [13, 67], 72: [23, 29]}, {86: [13, 61, 17, 29], 72: [23, 29]}, {86: [13, 61, 17, 29], 72: [23, 29]}, {86: [13, 61, 17, 29], 72: [23, 29]}, {86: [13, 67, 17, 29], 73: [19, 37]}, {86: [13, 67, 17, 29]}, {86: [13, 67, 17, 29]}, {86: [13, 67]}, {86: [13, 67]}, {86: [13, 67], 73: [17, 53]}, {86: [13, 67], 73: [17, 53]}, {86: [13, 67], 73: [17, 53]}, {87: [13, 61], 73: [17, 53, 23, 29]}, {87: [13, 61], 73: [17, 53, 23, 29]}, {87: [13, 61], 73: [17, 53, 23, 29]}, {87: [13, 61], 73: [17, 53, 23, 29]}, {87: [13, 61], 73: [17, 53, 23, 29]}, {87: [13, 67]}, {87: [13, 67]}, {87: [13, 67]}, {87: [13, 67]}, {87: [13, 67], 74: [23, 29]}, {87: [13, 67], 74: [23, 29]}, {88: [13, 61, 17, 29], 74: [23, 29]}, {88: [13, 61], 74: [17, 53, 23, 29]}, {88: [13, 61], 74: [17, 53, 23, 29]}, {88: [13, 61], 74: [17, 53, 23, 29]}, {88: [13, 61], 74: [17, 53, 23, 29]}, {88: [13, 61], 74: [17, 53, 23, 29]}, {88: [13, 61], 74: [17, 53, 23, 29]}, {88: [13, 67]}, {88: [13, 67]}, {88: [13, 67]}, {88: [13, 67]}, {89: [17, 29]}, {89: [17, 29]}, {89: [17, 29]}, {89: [17, 29]}, {89: [17, 29]}, {89: [17, 29]}, {89: [17, 29]}, {75: [17, 53, 23, 29]}, {75: [17, 53, 23, 29]}, {89: [13, 67]}, {89: [13, 67], 76: [23, 29]}, {76: [23, 29]}, {76: [23, 29]}, {76: [23, 29]}, {76: [23, 29]}, {76: [23, 29]}, {76: [23, 29]}, {76: [23, 29]}, {76: [23, 29]}, {76: [23, 29]}, {76: [23, 29]}, {76: [23, 29]}]
dicti = {}

def process1(n):
	dicti[0] = [1]
	for i in primes:
		if i > n:
			break
		else:
			key = int(n / i) - 1
			if key in dicti.keys():
				dicti[key].append(i)
			else:
				dicti[key] = [i]

def isProhibited(n, c):
	if c + 1 in prohibitedprimes[n - 1]:
		return True
	return False

def isCorrect(n, i, j):
	for itr in solutionofprimes[n - 1][i + 1]:
		if arr[j][inversemarkings[itr]] != 1:
			return False
	return True

def isMaxPower(n, b, v):
	if int(math.log(n, b)) == 1:
		return False
	elif v == int(math.log(n, b)) or v == int(math.log(n, b)) - 1:
		return True
	else:
		return False

def findMaxPowers(n):
	maxPowers = {}
	for itr in primes:
		if int(math.log(n, itr)) <= 1:
			break
		elif int(math.log(n, itr)) == 2:
			maxPowers[itr] = [int(math.log(n, itr))]
		else:
			maxPowers[itr] = [int(math.log(n, itr)) - 1, int(math.log(n, itr))]
	return maxPowers

def commonDivisors(a, b):
	if a > b:
		n = b
	else:
		n = a
	count = 0
	for d in range(1, n + 1):
		if a % d == 0 and b % d == 0:
			count += 1
	return count

def makeGrid(n):
	a = []
	for i in range(n):
		a.append([])
		for j in range(n):
			if i != j:
				a[i].append(commonDivisors(i + 1, j + 1))
			else:
				a[i].append(0)
	return a

def rotate(l, y=1):
	if len(l) == 0:
		return l
	y = -y % len(l)
	return l[y:] + l[:y]
for _ in range(int(input())):
	n = int(input())
	arr = []
	for i in range(n):
		arr.append(list(map(int, input().split())))
	markings = []
	inversemarkings = {}
	for i in range(n):
		markings.append(-1)
	data = []
	for i in range(n):
		data.append([])
	for i in range(n):
		data[i].append(max(arr[i]))
	process1(n)
	primeMarkings = []
	prohibited = {}
	for i in range(n):
		if data[i][0] == 1:
			markings[i] = dicti[0][len(dicti[0]) - 1]
			inversemarkings[dicti[0][len(dicti[0]) - 1]] = i
			del dicti[0][len(dicti[0]) - 1]
		elif data[i][0] == 2:
			c = arr[i].count(2)
			if not isProhibited(n, c):
				if c in dicti.keys():
					markings[i] = dicti[c][len(dicti[c]) - 1]
					inversemarkings[dicti[c][len(dicti[c]) - 1]] = i
					del dicti[c][len(dicti[c]) - 1]
					if dicti[c] == []:
						del dicti[c]
			elif c in prohibited.keys():
				prohibited[c].append(i)
			else:
				prohibited[c] = [i]
	for i in prohibited.keys():
		for j in prohibited[i]:
			if isCorrect(n, i, j):
				markings[j] = dicti[i][len(dicti[i]) - 1]
				inversemarkings[dicti[i][len(dicti[i]) - 1]] = j
	k = 0
	for i in arr:
		tk = []
		for key in inversemarkings.keys():
			if i[inversemarkings[key]] > 1:
				tk.append(key)
		data[k].append(tk)
		k += 1
	maxPowers = findMaxPowers(n)
	k = 0
	for itr in data:
		if len(itr[1]) == 1:
			v = itr[0] - 1
			if isMaxPower(n, itr[1][0], v):
				markings[k] = itr[1][0] ** maxPowers[itr[1][0]][0]
				inversemarkings[itr[1][0] ** maxPowers[itr[1][0]][0]] = k
				del maxPowers[itr[1][0]][0]
			else:
				markings[k] = itr[1][0] ** v
				inversemarkings[itr[1][0] ** v] = k
		k += 1
	k = 0
	for itr in data:
		if len(itr[1]) >= 2:
			number = 1
			for tk in itr[1]:
				p = 2
				i = tk
				if int(math.log(n, tk)) - 1 == 0:
					num = tk
				else:
					num = tk ** int(math.log(n, tk))
				while i <= tk ** int(math.log(n, tk)):
					if arr[k][inversemarkings[i]] == p:
						number *= tk
					else:
						break
					p += 1
					i *= tk
			markings[k] = number
			inversemarkings[number] = k
		k += 1
	if n == 1:
		print(1)
	else:
		for i in markings:
			print(i)


from math import sqrt
from collections import defaultdict

def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)

def countDivisors(a, b):
	G = gcd(a, b)
	SQ = int(sqrt(G))
	C = 0
	for i in range(1, SQ + 1):
		if G % i == 0:
			if i * i == G:
				C += 1
			else:
				C += 2
	return C
BigList = defaultdict(int)
ARR1 = [[0 for j in range(1001)] for i in range(1001)]
ctr = 0
for i in range(1, 1001):
	for j in range(1, 1001):
		if j == i:
			ARR1[i][j] = 0
		else:
			ARR1[i][j] = countDivisors(i, j)
for _ in range(int(input())):
	N = int(input())
	L = [[] for x in range(N)]
	for i in range(N):
		L[i].extend(list(map(int, input().split())))
	RefList = [[] for x in range(1000)]
	countDivisors = [0 for x in range(50)]
	for i in range(N):
		for j in range(50):
			countDivisors[j] = 0
		for j in range(N):
			countDivisors[ARR1[i + 1][j + 1]] += 1
		S = ''
		for j in range(1, 50):
			if countDivisors[j] > 0:
				S += str(j) + '=' + str(countDivisors[j]) + ' '
		C = BigList[S]
		if C == 0:
			ctr += 1
			BigList[S] = ctr
			C = ctr
		RefList[C].append(i + 1)
	Found = []
	for i in range(N):
		for j in range(50):
			countDivisors[j] = 0
		for j in range(N):
			countDivisors[L[i][j]] += 1
		S = ''
		for j in range(1, 50):
			if countDivisors[j] > 0:
				S += str(j) + '=' + str(countDivisors[j]) + ' '
		C = BigList[S]
		Flag = 1
		for x in range(len(RefList[C])):
			ele = RefList[C][x]
			if ele == -1:
				continue
			for (pos, num) in Found:
				if L[i][pos] != ARR1[num][ele]:
					Flag = 0
					break
			if Flag == 1:
				Found.append((i, ele))
				RefList[C][x] = -1
			else:
				Flag = 1
	Found.sort()
	for (pos, num) in Found:
		print(num)


pmax = 1100

def factorization(n, ans):
	if n == 1:
		return ans
	for p in primes:
		if p > n:
			break
		if n % p == 0:
			ans.append(p)
			return factorization(n // p, ans)

def gcd(a, b):
	if a < b:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)

def n_div(n):
	ans = 0
	for i in range(1, n + 1):
		if n % i == 0:
			ans += 1
	return ans
is_prime = [True] * pmax
for i in range(2, pmax):
	if is_prime[i]:
		for j in range(2, pmax // i + 1):
			if i * j < pmax:
				is_prime[i * j] = False
primes = []
for i in range(2, pmax):
	if is_prime[i]:
		primes.append(i)
q = int(input())
for qq in range(q):
	n = int(input())
	dmax = 80
	counts_old = []
	a = [[0] * dmax]
	for i in range(n):
		tmp = [0] * dmax
		a_tmp = [0]
		a_tmp.extend([int(k) for k in input().split()])
		for j in range(1, n + 1):
			if a_tmp[j] != 0:
				tmp[dmax - 1 - a_tmp[j]] += 1
		counts_old.append((tmp, i + 1))
		a.append(a_tmp)
	if n == 1:
		print(1)
		continue
	counts_old.sort()
	counts_old.append(([0] * dmax, 0))
	ndiv = [0]
	for i in range(1, n + 1):
		ndiv.append(n_div(i))
	counts = []
	for i in range(1, n + 1):
		tmp = [0] * dmax
		for j in range(1, n + 1):
			if j != i:
				tmp[dmax - ndiv[gcd(i, j)] - 1] += 1
		counts.append((tmp, i))
	counts.sort()
	counts.append(([0] * dmax, 0))
	assign = [-1] * (n + 1)
	nodes = [-1] * (n + 1)
	prime_labels = set()
	batch_labels = {counts[0][1]}
	batch = {counts_old[0][1]}
	for i in range(n):
		batch_labels.add(counts[i][1])
		batch.add(counts_old[i][1])
		if counts[i][0] != counts[i + 1][0]:
			for label in batch_labels:
				for row in batch:
					flag = True
					for p in factorization(label, []):
						if nodes[p] != -1 and a[row][nodes[p]] == 1:
							flag = False
							break
					for p in prime_labels.difference(factorization(label, [])):
						if a[row][nodes[p]] != 1:
							flag = False
							break
					if flag:
						assign[row] = label
						nodes[label] = row
						batch.remove(row)
						if is_prime[label]:
							prime_labels.add(label)
						break
			batch_labels = {counts[i + 1][1]}
			batch = {counts_old[i + 1][1]}
	for i in range(1, n + 1):
		print(assign[i])


from math import floor
from itertools import *

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def common(a, b):
	n = gcd(a, b)
	result = 0
	if a == b:
		return result
	for i in range(1, floor(n ** 0.5) + 1):
		if n % i == 0:
			if n // i == i:
				result += 1
			else:
				result += 2
	return result
arr = []
val = 1000
for a in range(1, val + 1):
	arr1 = []
	for b in range(1, val + 1):
		arr1.append(common(a, b))
	arr.append(arr1)
for t in range(int(input())):
	n = int(input())
	matrix = []
	(dic, arr1) = ([], [])
	for i in range(n):
		array = list(map(int, input().split()))
		matrix.append(array)
	for i in range(n):
		arr2 = [0] * 25
		for j in range(n):
			arr2[arr[i][j]] += 1
		arr3 = {}
		for j in range(25):
			if arr2[j]:
				arr3.update({j: arr2[j]})
		arr1.append(arr3)
	label1 = [0] * n
	for i in range(n):
		if label1[i]:
			continue
		for j in range(i + 1, n):
			flag = 1
			if len(arr1[i]) != len(arr1[j]):
				flag = 0
				continue
			for (x_values, y_values) in zip(arr1[i].items(), arr1[j].items()):
				if x_values != y_values:
					flag = 0
					break
			if flag:
				label1[j] = 1
				label1[i] = 1
	for i in range(n):
		arr2 = [0] * 25
		for j in matrix[i]:
			arr2[j] += 1
		arr3 = {}
		for j in range(25):
			if arr2[j]:
				arr3.update({j: arr2[j]})
		dic.append(arr3)
	label2 = [-1] * n
	for i in range(n):
		if label1[i] == 0 or len(arr1[i]) == 2:
			for j in range(n):
				flag = 1
				if len(dic[j]) != len(arr1[i]) or label2[j] != -1:
					flag = 0
					continue
				for (x_values, y_values) in zip(arr1[i].items(), dic[j].items()):
					if x_values != y_values:
						flag = 0
						break
				if flag:
					label2[j] = i
					break
	for i in range(n):
		if label1[i] == 0 or len(arr1[i]) == 2:
			continue
		for j in range(n):
			flag = 1
			if len(dic[j]) != len(arr1[i]) or label2[j] != -1:
				flag = 0
				continue
			for (x_values, y_values) in zip(arr1[i].items(), dic[j].items()):
				if x_values != y_values:
					flag = 0
					break
			if flag:
				flag1 = 0
				for k in range(n):
					if label2[k] != -1 and matrix[j][k] != arr[i][label2[k]]:
						flag1 = 1
				if not flag1:
					label2[j] = i
					break
	for i in range(n):
		print(label2[i] + 1)


import hashlib as hlib
from random import shuffle
from itertools import product

def gen_primes():
	primes = []
	num___is_prime = [True for i in range(1001)]
	num___is_prime[0] = False
	num___is_prime[1] = False
	for num in range(1001):
		if not num___is_prime[num]:
			continue
		primes.append(num)
		for mult in range(num * 2, 1001, num):
			num___is_prime[mult] = False
	return primes

def gen_test_n(num1_num2__cd_nr, n):
	r_sh = list(range(1, n + 1))
	shuffle(r_sh)
	ans = [['?' for j in range(n)] for i in range(n)]
	for (i, j) in product(range(n), repeat=2):
		ans[i][j] = num1_num2__cd_nr[r_sh[i]][r_sh[j]]
	return ans

def iteration(num1_num2__cd_nr, node_idx___curr_idea, node_idx___neigh_cd_nrs):
	nodes_nr = len(node_idx___curr_idea)
	node_idx___id = [None for x in range(nodes_nr)]
	num___id = [None for x in range(nodes_nr + 1)]
	num___is_known = [False for i in range(nodes_nr + 1)]
	for num in node_idx___curr_idea:
		if num != '?':
			num___is_known[num] = True
	for num in range(1, nodes_nr + 1):
		known_cds = []
		unknown_cds = []
		for (num2, cd_nr) in enumerate(num1_num2__cd_nr[num]):
			if num2 > nodes_nr:
				break
			if num___is_known[num2]:
				known_cds.append(cd_nr)
			else:
				unknown_cds.append(cd_nr)
		hash1 = hash(tuple(known_cds))
		hash2 = hash(tuple(sorted(unknown_cds[1:])))
		num___id[num] = (hash1, hash2)
	for node_idx in range(nodes_nr):
		known_cds = []
		unknown_cds = []
		for (idx, cd_nr) in enumerate(node_idx___neigh_cd_nrs[node_idx]):
			if node_idx___curr_idea[idx] == '?':
				unknown_cds.append(cd_nr)
			else:
				known_cds.append((node_idx___curr_idea[idx], cd_nr))
		known_cds = [x[1] for x in sorted(known_cds)]
		hash1 = hash(tuple(known_cds))
		hash2 = hash(tuple(sorted(unknown_cds)))
		node_idx___id[node_idx] = (hash1, hash2)
	id___primes = {}
	for prime in gen_primes():
		if prime * prime <= nodes_nr or 2 * prime > nodes_nr:
			continue
		if prime in node_idx___curr_idea:
			continue
		curr_id = num___id[prime]
		if curr_id not in id___primes:
			id___primes[curr_id] = []
		id___primes[curr_id].append(prime)
	for id1 in id___primes:
		curr_left = len(id___primes[id1])
		for node_idx in range(nodes_nr):
			if node_idx___id[node_idx] == id1:
				curr_left -= 1
				node_idx___curr_idea[node_idx] = id___primes[id1][curr_left]
			if curr_left == 0:
				break
	curr_id___num = {}
	for (num, id1) in enumerate(num___id):
		if id1 not in curr_id___num:
			curr_id___num[id1] = num
		else:
			curr_id___num[id1] = '?'
	for (idx, id1) in enumerate(node_idx___id):
		if node_idx___curr_idea[idx] != '?':
			continue
		node_idx___curr_idea[idx] = curr_id___num[id1]
	return node_idx___curr_idea

def first_iteration(num1_num2__cd_nr, node_idx___curr_idea, node_idx___neigh_cd_nrs):
	nodes_nr = len(node_idx___curr_idea)
	node_idx___id = [None for x in range(nodes_nr)]
	num___id = [None for x in range(nodes_nr + 1)]
	num___is_known = [False for i in range(nodes_nr + 1)]
	for num in node_idx___curr_idea:
		if num != '?':
			num___is_known[num] = True
	for num in range(1, nodes_nr + 1):
		known_cds = []
		unknown_cds = []
		for (num2, cd_nr) in enumerate(num1_num2__cd_nr[num]):
			if num2 > nodes_nr:
				break
			if num___is_known[num2]:
				known_cds.append(cd_nr)
			else:
				unknown_cds.append(cd_nr)
		hash1 = hash(tuple(known_cds))
		hash2 = hash(tuple(sorted(unknown_cds[1:])))
		num___id[num] = (hash1, hash2)
	for node_idx in range(nodes_nr):
		known_cds = []
		unknown_cds = []
		for (idx, cd_nr) in enumerate(node_idx___neigh_cd_nrs[node_idx]):
			if node_idx___curr_idea[idx] == '?':
				unknown_cds.append(cd_nr)
			else:
				known_cds.append((node_idx___curr_idea[idx], cd_nr))
		known_cds = [x[1] for x in sorted(known_cds)]
		hash1 = hash(tuple(known_cds))
		hash2 = hash(tuple(sorted(unknown_cds)))
		node_idx___id[node_idx] = (hash1, hash2)
	primes = gen_primes()
	for prime in primes:
		if prime * prime > nodes_nr:
			break
		x = prime
		k = 1
		while True:
			if x * prime > nodes_nr:
				break
			x *= prime
			k += 1
		id1 = num___id[x]
		id2 = num___id[x // prime]
		if 2 * x <= nodes_nr:
			continue
		x //= prime
		if id1 != id2:
			raise Exception('Unbelivable! id1 != id2')
			return
		replaces_count = 0
		for node_idx in range(nodes_nr):
			if node_idx___id[node_idx] == id1:
				node_idx___curr_idea[node_idx] = x
				replaces_count += 1
				x *= prime
			if replaces_count > 1:
				break
	curr_id___num = {}
	for (num, id1) in enumerate(num___id):
		if id1 not in curr_id___num:
			curr_id___num[id1] = num
		else:
			curr_id___num[id1] = '?'
	for (idx, id1) in enumerate(node_idx___id):
		if node_idx___curr_idea[idx] != '?':
			continue
		node_idx___curr_idea[idx] = curr_id___num[id1]
	return node_idx___curr_idea

def fill_primes(node_idx___curr_idea, node_idx___neigh_cd_nrs):
	n = len(node_idx___curr_idea)
	primes = gen_primes()
	curr_prime_idx = -1
	for (idx, prime) in enumerate(primes):
		if prime > n // 2:
			curr_prime_idx = idx
			break
	one_flag = True
	for node_idx in range(n):
		cd_nrs = set(node_idx___neigh_cd_nrs[node_idx])
		if len(cd_nrs) == 2:
			if one_flag:
				node_idx___curr_idea[node_idx] = 1
				one_flag = False
			else:
				node_idx___curr_idea[node_idx] = primes[curr_prime_idx]
				curr_prime_idx += 1

def solve(num1_num2__cd_nr):
	nodes_nr = int(input())
	node_idx___neigh_cd_nrs = [[] for x in range(nodes_nr)]
	for node_idx in range(nodes_nr):
		node_idx___neigh_cd_nrs[node_idx] = [int(x) for x in input().split()]
	node_idx___curr_idea = ['?' for x in range(nodes_nr)]
	fill_primes(node_idx___curr_idea, node_idx___neigh_cd_nrs)
	first_iteration(num1_num2__cd_nr, node_idx___curr_idea, node_idx___neigh_cd_nrs)
	for i in range(2):
		iteration(num1_num2__cd_nr, node_idx___curr_idea, node_idx___neigh_cd_nrs)
	print(*node_idx___curr_idea, sep='\n')
reqs_nr = 1
curr_size = 1001
num1_num2__cd_nr = [[0 for x in range(curr_size)] for x in range(curr_size)]
for cd in range(1, curr_size):
	for num1 in range(cd, curr_size, cd):
		for num2 in range(num1 + cd, curr_size, cd):
			num1_num2__cd_nr[num1][num2] += 1
			num1_num2__cd_nr[num2][num1] += 1
reqs_nr = int(input())
for req in range(reqs_nr):
	solve(num1_num2__cd_nr)