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

见题面

见题面