# Similar Rotations

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

## Description

In mathematics especially in Euclidean geometry, we often notice rotations and corresponding rotation matrices. The dimension of the whole space of three dimensional rotation matrices is three. A natural problem is, how to measure the space. It is no doubt that the space is a metirc space if we measure the distance of two rotations as the maximum distance of two images for a point on the unit sphere.
We define the distance dist(p,q) of two points p, q on the unit sphere as the length of shortest path along the surface of unit sphere. For each two rotations $R_1$ and $R_2$ one can find the point p on the unit sphere with the largest $L_{R_1,R_2}$ = dist$(R_1(p),R_2(p))$.We define $L_{R_1,R_2}$ as the distance of rotations $R_1$ and $R_2$.
Here we have several three dimensional rotation matrices. For each one of them, please find another one of them with the shortest distance to it in this metric space.

## Input

There are no more than 100 cases. For each case, the first line consists an integer n (1 ≤ n ≤ 100), which is the number of rotation matrics. Each of the following n lines consists 9 float-point numbers 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) with six decimal places corresponding to the a rotation matrix R.

## Output

For each test case, output one line with n float-point numbers. The i-th one is the shortest distance to the i-th rotation from another one of them. The answer should be rounded to two decimal places

## Sample Input

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

## Sample Output

1.57 1.57 1.57 1.57 0.79 0.79 0.79 1.57

jiangzijing2015

## Source

2016ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学）