在数学（尤其是欧几里得几何）中，我们经常会注意到旋转以及相应的旋转矩阵。

三维旋转矩阵所构成的整个空间的维度是三。一个自然的问题是，如何度量这个空间。毫无疑问，如果我们定义两个旋转之间的距离为单位球面上任意一点在两种旋转下的像的最大距离，那么该空间就是一个度量空间。

具体来说，我们定义单位球面上两点 $p$ 和 $q$ 之间的距离 $dist(p,q)$ 为沿单位球面表面的最短路径长度。对于两个旋转 $R_1$ 和 $R_2$，我们可以找到单位球面上使得 $dist(R_1(p),R_2(p))$ 最大的点 $p$。

现在我们有若干个三维旋转矩阵。对于其中的每一个旋转矩阵，请在这个度量空间中找到另一个与之距离最短的旋转矩阵。

输入格式

输入包含不超过 $100$ 组测试数据。

对于每组测试数据，第一行包含一个整数 $n$（$1\le n\le 100$），表示旋转矩阵的数量。

接下来的 $n$ 行，每行包含 $9$ 个保留六位小数的浮点数 $R(0,0),R(0,1),R(0,2),R(1,0),R(1,1),R(1,2),R(2,0),R(2,1),R(2,2)$，对应一个旋转矩阵 $R$。

输出格式

对于每组测试数据，输出一行，包含 $n$ 个浮点数。第 $i$ 个数表示第 $i$ 个旋转矩阵与其他旋转矩阵之间的最短距离。答案应四舍五入保留两位小数。

任何与标准答案相差不超过 0.01 的输出都将被判定为正确。

样例

输入样例 1

4
1.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 1.000000
1.000000 0.000000 0.000000 0.000000 0.000000 -1.000000 0.000000 1.000000 0.000000
1.000000 0.000000 0.000000 0.000000 -1.000000 -0.000000 0.000000 0.000000 -1.000000
1.000000 0.000000 0.000000 0.000000 -0.000000 1.000000 0.000000 -1.000000 -0.000000
4
1.000000 0.000000 0.000000 0.000000 0.000000 -1.000000 0.000000 1.000000 0.000000
1.000000 0.000000 0.000000 0.000000 -0.707107 -0.707107 0.000000 0.707107 -0.707107
1.000000 0.000000 0.000000 0.000000 -1.000000 -0.000000 0.000000 0.000000 -1.000000
1.000000 0.000000 0.000000 0.000000 -0.000000 1.000000 0.000000 -1.000000 -0.000000

输出样例 1

1.57 1.57 1.57 1.57 
0.79 0.79 0.79 1.57