#include <iostream>

 #include <vector>

 #include <algorithm>

 #include <string>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <cstdlib>

 #include <queue>

 #include <stack>

 #include <map>

 #include <set>

 using namespace std;

 const int N=;

 const int MOD=;

 char g[N][N];

 int dp[][N][N];

 void add(int &a,int b) {

     a+=b;

     while (a>MOD)

         a-=MOD;

 }

 int main () {

     int T;

     scanf("%d",&T);

     while (T--) {

         int n;

         scanf("%d",&n);

         for (int i=;i<=n;i++) {

             scanf("%s",g[i]+);

             for (int j=;j<=n;j++) {

                 dp[][i][j]=;

                 dp[][i][j]=;

             }

         }

         if (g[][]!=g[n][n]){

             puts("");

             continue;

         }

         int s=;

         dp[s][][n]=;

         int ret=;

         for (int k=;k<=n;k++) {

             s^=;

             for (int j1=,i1=k;j1<=k;j1++,i1--) {

                 for (int j2=n,i2=n-k+;j2>=n-k+;j2--,i2++) {

                     dp[s][j1][j2]=;

                 }

             }

             for (int j1=,i1=k;j1<=k;j1++,i1--) {

                 for (int j2=n,i2=n-k+;j2>=n-k+;j2--,i2++) {

                     if (g[i1][j1]!=g[i2][j2]) continue;

                         add(dp[s][j1][j2],dp[s^][j1][j2]);

                         add(dp[s][j1][j2],dp[s^][j1-][j2]);

                         add(dp[s][j1][j2],dp[s^][j1-][j2+]);

                         add(dp[s][j1][j2],dp[s^][j1][j2+]);

                 }

             }

         }

         for (int j=;j<=n;j++)

             add(ret,dp[s][j][j]);

         printf("%d\n",ret);

     }

     return ;

 }