The WormWold puzzle was initially proposed by Cliff Pick- over in the Discover Magazine, issue of November 1994 (a visit to his home page is highly recommended!). The Worm- World 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 Worm- World, 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 ≤ 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 121 234 321 Sample Output 4