You are given a NxN matrix of 0's and 1's. A staircase is defined as a structure similar to the one given below filled with 1s.

Image Link : http://img546.imageshack.us/img546/7141/staircase.png

You are required to find the number of staircases of all heights greater than one in the given matrix. Since the answer can be very large, output the answer mod 10⁶ + 3.

Input

The first line of the input file contains T which denotes the number of test cases.The first line of each test case contains an integer N.Then N lines follow for each test case  where each of the lines contain N elements of the input array [NxN matrix].

T<=20 && N<=500;

Output

The output should contain T lines each line with the answer for each case.Print the answer modulo 10^6+3

Warning: Huge I/O

Example

Input:

2
3
1 1 1
1 1 1
1 1 1
2
1 0
1 1


Output:

5
1