Undercity's map can be seen as an n⋅m matrix, each cell of the matrix contains a lowercase English letter. A path is a sequence of cells such that two neighbouring cells share one edge and the next cell can be reached from the previous cell by only moving right or down.
The city is a little bit weird, so one can only travel through a palindromic path.
A palindromic path is a path such that if you view the letters on all the cells from the starting point to the ending point of the path as a sequence, the sequence is equal when you read from left to right and from right to left.
A way of covering is considered magic if and only if all cells of the matrix are covered by exactly one palindromic path.
Two magic coverings are considered different if and only if there is at least one cell that is covered by different paths in two ways.
Sylvanas believes it's a fulfilling mission to find the number of magic coverings in the city.
Let's help her to do it!
The input consists of multiple test cases.
The first line contains an integer T (1≤T≤10) denoting the number of test cases.
In each test case, the first line contains two integers n,m(n,m≤6), denoting the size of matrix.
The following n lines, each line contains mm lowercase English letters, describing the matrix.
2
2 2
ab
cd
2 2
aa
aa1
9