In mathematics especially in Eucilean 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.

Specifically, we define the distance $dist(p,q)$ of two point $p$, $q$ on the unit sphere as the length of shortest path along the surface of unit sphere. For two rotations $R_1$ and $R_2$ we can find the point $p$ on the unit sphere with the largest $dist(R_1(p),R_2(p))$.

Now we have several three dimensional rotation matrics. 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\le n\le 100$), which is the number of rotation matrics. Each of the following $n$ line 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.

Any outputs that differs the jury's answer by at most 0.01 will be considered correct.

Example

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

Output

1.57 1.57 1.57 1.57 
0.79 0.79 0.79 1.57