问题描述

Jam 进入了迷宫，他必须从中找到一条回文路径（1，1 ）​​到（N,N）走出迷宫。 但他不仅在思考如何走出迷宫，还在计算有多少种方法可以走出迷宫且路径上形成的字母是回文串。

迷宫是一个N∗ N网格。每个单元格上都有一个大写字母。 Jam 位于左上角（1，1 ）​​现在，出口在右下角（N,N）。Jam只能往下走或往右走。 考虑到回文路径的数量可能很大，你只需要输出模5201314。

输入

第一行是测试数据组数T（1≤T​​≤10 ）​。 对于每组测试数据： 第一行一个整数N（1≤N​​≤ 500 )表示迷宫的大小。 接下来输入N行，每行N个大写字母。

输出

对于每组测试数据，输出回文路径数量模5201314。

示例输入

1
4
ABCD
BEFE
CDEB
GCBA

示例输出

12

解释

有 1 条路径是“ABCDCBA” 有 1 条路径是“ABCGCBA” 有 4 条路径是“ABEDEBA” 有 6 条路径是“ABEFEBA”