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$.
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.
For each testcase, output the number of palindrome path mod $5201314$.
there are 1 solutions is"ABCDCBA"
there are 1 solutions is"ABCGCBA"
there are 4 solutions is"ABEDEBA"
there are 6 solutions is"ABEFEBA"