Chef And Land Labeling

All submissions for this problem are available.
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(N1)/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 ith of these lines contains N spaceseparated 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 ith of these lines should contain a single integer — the label of the ith 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
Author:  kamranmaharov 
Tester:  r_64 
Editorial  https://discuss.codechef.com/problems/CLANDLBL 
Tags  feb18, isomorphism, kamranmaharov , mediumhard, numbertheory 
Date Added:  6122017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 