Gilbert 是 Ginkgo 公司的网络管理员。他的老板对地板上杂乱的网络线缆感到非常恼火。最终，他找到 Gilbert，要求这位懒惰的网络管理员说明计算机和交换机是如何连接的。由于他是一名程序员，他非常不情愿在办公室里走来走去，用眼睛去检查线缆和交换机。相反，他选择通过测量和一点数学思维来完成这项工作，一直坐在电脑前。你的任务是通过编写一个程序，根据测量结果重建网络拓扑结构，来帮助他。

已知计算机的数量是确定的，而交换机的数量是未知的。每台计算机通过一根线缆连接到其中一个交换机，且不连接其他任何设备。具体来说，计算机永远不会直接连接到另一台计算机，也不会连接到两个或更多的交换机。交换机通过线缆连接形成一棵树（一个没有环的连通无向图）。没有“无用”的交换机。换句话说，每个交换机都位于至少一对计算机之间的路径上。

总而言之，计算机和交换机共同构成了一棵树，其中叶子节点是计算机，内部节点是交换机（见图 9）。

图 9：计算机和交换机

Gilbert 测量了所有计算机对之间的距离。两台计算机之间的距离简单地定义为它们路径上的交换机数量加一。或者等价地，它是连接它们所使用的线缆数量。你可能想知道 Gilbert 如何仅凭测量就能获得这些距离。好吧，他通过一种他发明的非常复杂的统计处理技术做到了这一点。请不要询问细节。

因此，你将获得一个描述树的叶子节点之间距离的矩阵。你的工作是从中构建出这棵树。

输入格式

输入是一系列距离矩阵，后跟一行仅包含 '0' 的行。每个距离矩阵的格式如下：

$N$ $a_{11} \quad a_{12} \quad \dots \quad a_{1N}$ $a_{21} \quad a_{22} \quad \dots \quad a_{2N}$ $\vdots \quad \vdots \quad \ddots \quad \vdots$ $a_{N1} \quad a_{N2} \quad \dots \quad a_{NN}$

$N$ 是矩阵的大小，即行数和列数。$a_{ij}$ 给出了第 $i$ 个叶子节点（计算机）和第 $j$ 个叶子节点之间的距离。你可以假设 $2 \le N \le 50$，且矩阵是对称的，其对角线元素均为零。即对于每个 $i$ 和 $j$，都有 $a_{ii} = 0$ 且 $a_{ij} = a_{ji}$。每个非对角线元素 $a_{ij}$ ($i \neq j$) 满足 $2 \le a_{ij} \le 30$。你可以假设总是有解的。也就是说，存在一棵具有给定叶子节点间距离的树。

输出格式

对于每个距离矩阵，找到一棵具有给定叶子节点间距离的树。然后输出每个内部节点的度数（即连接到每个交换机的线缆数量），所有度数应在同一行中按升序排列。行内的数字应由单个空格分隔。一行不应包含任何其他字符，包括行尾空格。

样例

输入 1

4
0 2 2 2
2 0 2 2
2 2 0 2
2 2 2 0
4
0 2 4 4
2 0 4 4
4 4 0 2
4 4 2 0
2
0 12
12 0
0

输出 1

4
2 3 3
2 2 2 2 2 2 2 2 2 2 2