Programming Assignment - Magic Squares

A Magic Square is an n × n matrix containing the numbers 1 to n2, each number occurring exactly once. The sum of each row, each column, and both diagonals is the same, and is equal to





The simplest magic square is the 1 × 1 magic square whose only entry is the number 1.


1


The next simplest is the 3 × 3 magic square





The earliest known magic square is Chinese, recorded around 2800 B.C. A Chinese book passes on the story called Lo Shu (book of the River Lo) which tells how a magic square on the back of a turtle saved the city. The square is a typical 3 × 3 magic square, except that the numbers were represented by patterns not numerals.

The best known magic square is probably the 4 × 4 square depicted in the engraving Melancholia, shown below. This woodcut was made by in 1514 by Albrecht Dürer, a contemporary of Leonardo da Vinci.

Dürer's Magic Square
Notice the date of the engraving on the bottom row.
16 3 2 13
5 10 11 8
9 6 7 12
4 15 14 1

Programming Assignment

In this problem you are to determine whether or not a given square is a Magic Square.

Input

Your program is to read the input from a file named "squares.in" stored in the default directory. The first line of the input file will contain a single integer indicating the number of squares to look at. The first line of input for each square will contain a single integer representing n, followed by n lines, each of which has n integers, separated by white space. The valid range for n is 1 ≤ n ≤ 50.

Output

All output is to be written to a file named "output.txt" located in the default directory. For each square you are to display the matrix, using uniform spacing for each column. Below the matrix you are to display a message. If the square is a Magic Square, the message should read "This is a Magic Square. The magic number is ", and then display the magic number. If the square is not a Magic Square, the message should read "This is not a Magic Square". Your output should follow the format shown in the Sample Output below.

Sample Input

2
3
1 8 6
3 5 7
4 9 2
4
16 3 2 13
5 10 11 8
9 6 7 12
4 15 14 1

Sample Output

    1    8    6

    3    5    7

    4    9    3

This is not a Magic Square.

 

   16    3    2   13

    5   10   11    8 

    9    6    7   12

    4   15   14    1

This is a Magic Square. The magic number is 34.