题目描述

对于一个字母矩阵，我们称矩阵中的一个递增序列是指在矩阵中找到两个字母，它们在同一行，同一列，或者在同一 45 度的斜线上，这两个字母从左向右看、或者从上向下看是递增的。

例如，如下矩阵中

LANN
QIAO

有 LN、LN、AN、AN、IO、AO、LQ、AI、NO、NO、AQ、IN、AN 等 13 个 递增序列。注意当两个字母是从左下到右上排列时，从左向右看和从上向下看是不同的顺序。

给你 $N$ 行 $M$ 列的矩阵，请问总共有多少个递增序列？

输入描述

第一行包一个整数 $T$，表示测试数据的规模。

每组测试数据第一行 2 个整数 $N,M$。 接下来 $N$ 行每行 $M$ 个大写字母。

输出描述

对每个输入输出一个整数表示答案。

1
2 4
LANN
QIAO

13

评测用例规模与约定：

对于所有评测用例，$1≤T≤10,1≤N,M≤100$。