Jam got into a maze, he has to find a palindrome path from $(1,1)$ to $(N,N)$ to get out.
However he is not only thinking about how to get out of the maze,
but also counting the number of ways he can get out.
The maze a $N*N$ grid. On each cell is a uppercase letter.
Jam is at upper-left corner $(1,1)$ now, and the exit is at lower-right corner $(N,N)$.
Jam can only go down or go right.
Considering the number of palindrome path may be huge, you just need to output the number mod $5201314$.
Input
The first line is $T(1 \leq T \leq 10)$ means $T$ Case.
For each case:
The first line is $N(1 \leq N \leq 500)$ means the size of the maze.
Then $N$ lines follow, each line has $N$ uppercase letter.
Output
For each testcase, output the number of palindrome path mod $5201314$.
Sample Input
1
4
ABCD
BEFE
CDEB
GCBA
Sample Output
12
Hint
there are 1 solutions is"ABCDCBA"
there are 1 solutions is"ABCGCBA"
there are 4 solutions is"ABEDEBA"
there are 6 solutions is"ABEFEBA"
