Ball Passing

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 :

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.
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 corre- sponding 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.
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.
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 below (corresponding to the first sample case). Set of players probably carrying the ball 9 5,8 2,6,7 1,3 1,3 2 Each player in the carrying set 9 5 8 2 6 7 1 3 1 3 2 BALL 1: Next Line 5,8 2,6,7 2,6,7 1,3 1,3 1,3 4 4 2,6,7 2,6,7 5,8 Corresponding RESULT set of players that the ball can be passed to. 5,8 PASSED 2 PASSED 2,6,7 PASSED 1 PASSED 1,3 PASSED 1,3 PASSED NILL REVERSE NILL REVERSE NILL HALT 2 PASSED NILL HALT

BALL 2: 2/3 Set of players probably carrying the ball 4 1,3 1,2 2 1 Each player in the carrying set 4 1 3 1 2 2 1 Next Line 1,3 2,6,7 2,6,7 4(Reversed) 5,8 1,3 4 Corresponding RESULT set of players that the ball can be passed to. 1,3 PASSED NILL REVERSE 2 PASSED NILL HALT NILL REVERSE 1 PASSED NILL HALT 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. Input 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 − 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. Output 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 at least one ball at least one point of time) ∗10∧9) with no leading zeros. If probability is p, output floor (p ∗ 10∧9). For case 1: probability is 0.166666666666666. Note: The picture on the right illustrates the fisrt sample case. Sample Input 4 3 9 58 267 13 4 6 3 9 58

3/3 267 13 4 3 2 1 23 4 2 4 15 14 13 16 10 12 11 7 2 4 195 68 3 7 Sample Output 166666666 583333333 500000000 291666666