解题思路

给定一个未知排列 $p=(p_1,\dots,p_n)$（由 $1..n$ 的所有数恰好一次组成），用它构造矩阵

$G_{i,j}$=$p_i$ $\times$ $p_j$ $(1\le i,j\le n)$

现在给出矩阵 $G$，需恢复排列 $p$。

关键观察：对任意一行 $i$，这一行所有元素的最大公约数为

题目内容

给定一个长度为 $n$ 的未知排列 $p$，小红使用它构造了一个 $n×n$ 的矩阵 $G$ ，满足：

对于所有 $1≤i,j≤n$，有 $G_{i,j}=p_i×p_j$ 。

现在，小红已经给出了矩阵 $G$，你能恢复排列 $p$ 吗。

【名词解释】 长度为 $n$ 的排列是由 $1,2,…,n$ 这 $n$ 个整数、按任意顺序组成的数组(每个整数均恰好出现一次)。例如， {$2,3,1,5,4$} 是一个长度为 $5$ 的排列，而 {$1,2,2$} 和 {$1,3,4$} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述

第一行包含整数 $t(1 ≤t≤ 10)$ ，表示测试用例数。

每个测试用例格式如下：

第一行包含整数 $n(1≤n≤200)$ ;

接下来 $n$ 行，每行包含 $n$ 个整数，表示矩阵 $G$ 的一行，满足 $1≤ G_{i,j}≤ n^2$ ?

输出描述

对每个测试用例，输出一行 $n$ 个整数 $p_1,p_2,...,p_n$，表示恢复出的排列。保证答案存在。

样例1

输入

2
3
1 2 3
2 4 6
3 6 9
4
1 4 3 2
4 16 12 8
3 12 9 6
2 8 6 4

输出

1 2 3
1 4 3 2