Worm World 

The WormWold puzzle was initially proposed by Cliff Pickover in the Discover Magazine, issue of November 1994 (a visit to his home page is highly recommended!). The WormWorld is a grid of numbers and it is a tough place to live in. The worms that inhabit it are all born with nasty allergies. The first time they come in contact with a number, their immune systems are overstimulated; if they are exposed to that number a second time, they die of anaphylactic shock.

A worm can start crawling on any square in WormWorld, and it can then move horizontally or vertically but not diagonally. In this scenario, what is the longest path a worm can take without dying? An example is illustrated in the following figure.

Write a program that determines the largest path a worm can take for a given grid.

Input 

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The first input line is the size N of the grid ( 0 < N$\le$12). This is followed by N input lines, each one with N positive integer values separated by blank spaces (as a simplification, we will only use grid values less then 1000).

Output 

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

The output is the size (in terms of the number of squares) of the largest path that a worm can take.

Sample Input 

1

3
1 2 1
2 3 4
3 2 1

Sample Output 

4