——你在《魔兽世界》里因为从幽暗城的电梯上掉下去死过多少次？ ——你在那迷宫般的城市里穿行却找不到拍卖行多少次了？ ——幽暗城本身就是一个迷宫！

幽暗城的地图可以看作一个 $n \times m$ 的矩阵，矩阵的每个单元格包含一个小写英文字母。路径是一个单元格序列，其中相邻的两个单元格共享一条边，且只能通过向右或向下移动从前一个单元格到达下一个单元格。

这座城市有点奇怪，人们只能通过回文路径旅行。

回文路径是指这样一条路径：如果你将路径上从起点到终点的所有单元格中的字母视为一个序列，该序列从左向右读和从右向左读是相同的。

如果矩阵中的所有单元格都被恰好一条回文路径覆盖，则称这种覆盖方式为“魔法覆盖”。

如果存在至少一个单元格在两种覆盖方式中被不同的路径所覆盖，则认为这两种魔法覆盖是不同的。

希尔瓦娜斯认为找到城市中魔法覆盖的数量是一项很有成就感的任务。 让我们帮她完成吧！

输入格式

输入包含多个测试用例。 第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n, m$ ($n, m \le 6$)，表示矩阵的大小。 接下来的 $n$ 行，每行包含 $m$ 个小写英文字母，描述该矩阵。

输出格式

对于每个测试用例，输出一行包含一个整数，表示答案。

样例

样例输入 1

2
2 2
ab
cd
2 2
aa
aa

样例输出 1

1
9