1256: Beautiful Garden
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 2 Solved: 2
[Submit] [Status] [Web Board] [Creator:]
Description
There's a beautiful garden whose size is n × m in Edward's house. The garden can be partitioned into n × m equal-sized square chunks. There are some kinds of flowers planted in each square chunk which can be represented by using lowercase letters.
However, Edward thinks the garden is not beautiful enough. Edward wants to build a water pool in the garden. So that the garden would look like symmetric (both horizontally and vertically). The water pool is a rectangle whose size is p × q and the center of the water pool is also the center of the garden.
Something else important you should know is:
n, m, p and q are all even.
p is always less than n.
q is always less than m.
The borders of the water pool are parallel to the border of garden.
Edawrd wants to know how many different pairs of (p, q) he can choose.
However, Edward thinks the garden is not beautiful enough. Edward wants to build a water pool in the garden. So that the garden would look like symmetric (both horizontally and vertically). The water pool is a rectangle whose size is p × q and the center of the water pool is also the center of the garden.
Something else important you should know is:
n, m, p and q are all even.
p is always less than n.
q is always less than m.
The borders of the water pool are parallel to the border of garden.
Edawrd wants to know how many different pairs of (p, q) he can choose.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains two integers n and m (1 <= n, m <= 2000, n and m are even), indicating the size of the garden. For next n lines, each line contains m characters showing the garden.
It is guaranteed that only lowercase letters will appear.
The first line contains two integers n and m (1 <= n, m <= 2000, n and m are even), indicating the size of the garden. For next n lines, each line contains m characters showing the garden.
It is guaranteed that only lowercase letters will appear.
Output
For each test case, output an integer indicating the number of choices to build the water pool.
Sample Input Copy
3
6 8
acbbbbca
dcaccacd
cdaddadc
cdaddadc
dcaccacd
acbbbbca
6 8
acbcbbca
dcaccacd
cdaddadc
cdaddadc
dcaccacd
acbbbbca
6 8
acbbbbca
dcadcacd
cdaddadc
cdaddadc
dcaccacd
acbbbbca
Sample Output Copy
6
0
3
HINT
For the first sample, you have following six choices (blank rectangle means the water pool):