Problem F : Ball Passing 
Time Limit : 2 seconds 
	A new game is introduced. This game involves a perfect square number of players. 
Now, say n*n players participate in the game. These players have a unique number each which ranges 
from 1 to n*n both inclusive. The number is printed in the front and back of their T-Shirts. 
These n*n players arrange themselves such that the boundary formed by the whole set of players 
looks like an oval.

	The game involves 2 balls. One ball is given to player in the first line and one ball 
to player in the last line. Both the balls are passed towards the other corner as follows :

1. If there is no more line in the direction of passing, then the ball passing continues in the 
   opposite direction. 
	NOTE : However , direction reversal takes place only once . Passing gets halted when 
		this condition occurs second time instead of changing the direction.

2. The player carrying the ball passes the ball to the player, chosen at random from the set 
  of players satisfying both the conditions below :
  2.1. The set of players consists of players in next line in the direction of passing for the 
       corresponding ball.
  2.2. Each player in the set of players has number less than the number of person carrying 
       the ball.
 This is followed if the set contains at least one player.

3. If the set of players formed by the above rules has no players, then the direction of passing 
   is reversed for the ball and the person carrying the ball obviously starts the passing 
   in that direction for that ball. 
	NOTE : However , direction reversal takes place only once . Passing gets halted when 
              this condition occurs second time instead of changing the direction.

4. When passing is halted for both the balls, the game comes to end.



The following tables illustrate the possible movements for each ball for the instance shown above .





	Given the number n, the arrangement of n*n players and the player number p , return the 
probability that the player numbered p holds atleast one ball at atleast one point of time 
during the course of the game.

CONSTRAINTS :
 The first line in the input file contains no. of test cases (<30).
 Each test case is separated by an empty line. 
 Each test case satisfies the following conditions :
  : Value of n(first line) ranges from 2 to 20 both inclusive.
  : Arrangement is represented by 2*n-1 lines ; Lines 1 to n have space separated list of 
    i integers where i is the line number ; Lines n+1 to 2*n-1 have 2*n-i integers in 
    space separated manner. 
  : Each integer in arrangement lies between 1 and n*n inclusive.
  : Each integer occurs only once in arrangement (Unique).
  : The player number(line following the arrangement) lies between 1 and n*n both inclusive.
  : The output should contain one line for every test case.
  : Each line in the output must be an integer ,the floor value of ((The required probability (that player  p holds atleast 
    one ball atleast one point of time)*10^9) with no leading zeros .
  : If probability is p, output floor(p*10^9).

Sample Input :
4
3
9
5 8
2 6 7
1 3
4
6

3
9
5 8
2 6 7
1 3
4
3

2
1
2 3
4
2

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

Sample Output:
166666666
583333333
500000000
291666666

For case 1: probability is 0.166666666666666.


Problem Setter : Ramgopal K
Written for Samhita '08