Description

In linear algebra, LU decomposition is a type of matrix decomposition that can decompose a matrix into the product of a unit-down triangular matrix and an upper triangular matrix (sometimes the product of them and a permutation matrix). The LU decomposition is mainly used in numerical analysis to solve linear equations, inverse matrices, or to calculate determinants.

In essence, LU decomposition is an expression of Gaussian elimination. First, the matrix A is transformed into an upper triangular matrix by elementary row transformation. For students who have studied linear algebra, this process should be very familiar. In the linear algebra test, solving the determinant inversion is usually done in this way. Then, the original matrix A is transformed into an upper triangular matrix, and the corresponding transformation matrix is a lower triangular matrix. The middle process is the Doolittle algorithm. A is a matrix, A = LU, where the corresponding element of A has been given. The LU value can be calculated directly in order. A matrix is obtained by multiplying L matrix by U matrix.

tip:Calculated in order of color

Format

Input

Input contains multiple test cases.The first line gives a positive integer n, 2<n<10, representing a matrix of n rows and n columns. In the following n rows, n integers are input in each row, and the range of integers is in the 32-bit integer.

Output

For each test case,The sum of the L matrix + U matrix is output, and the decimal point in the output matrix remains three digits.

Samples

3
3 2 5
-1 4 3
1 -1 3

4.000 2.000 5.000
-0.333 5.667 4.667
0.333 -0.357 4.000

Hint