#include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int maxn = ;

 const int mod = ;

 int dp[maxn][maxn][];

 char str[maxn][maxn];

 int n;

 void init() {

     memset(dp, , sizeof(dp));

 }

 inline int add(int x, int y) {

     x += y;

     if (x > mod) x -= mod;

     return x;

 }

 int main() {

     int tc;

     scanf("%d", &tc);

     while (tc--) {

         init();

         scanf("%d", &n);

         for (int i = ; i <= n; i++) scanf("%s", str[i] + );

         if (str[][] == str[n][n]) dp[][n][] = ;

         //printf("dp[1][n][0]:%d\n", dp[1][n][0]);

         int u = ;

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

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

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

                     int x1, y1, x2, y2;

                     x1 = j; y1 = i +  - x1;

                     x2 = n +  - k; y2 =  * n - i +  - x2;

                     //滚动数组非常需要注意的地方就是！！！每次都要初始化！！！初始化！！！初始化！！！

                     dp[x1][x2][u] = ;

                     //if (i == n&&x1 != x2) continue;

                     if (str[x1][y1] == str[x2][y2]) {

                         //printf("fuck!");

                         int &cur = dp[x1][x2][u];

                         cur = add(cur, dp[x1][x2][!u]);

                         cur = add(cur, dp[x1][x2 + ][!u]);

                         cur = add(cur, dp[x1 - ][x2][!u]);

                         cur = add(cur, dp[x1- ][x2 + ][!u]);

                     }

                 }

             }

             u = !u;

         }

         int ans = ;

         for (int i = ; i <= n; i++) ans = add(ans, dp[i][i][!u]);

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

     }

     return ;

 }