403284: GYM101102 D Rectangles

Given an R×C grid with each cell containing an integer, find the number of subrectangles in this grid that contain only one distinct integer; this means every cell in a subrectangle contains the same integer.

A subrectangle is defined by two cells: the top left cell (r₁, c₁), and the bottom-right cell (r₂, c₂) (1 ≤ r₁ ≤ r₂ ≤ R) (1 ≤ c₁ ≤ c₂ ≤ C), assuming that rows are numbered from top to bottom and columns are numbered from left to right.

The first line of input contains a single integer T, the number of test cases.

The first line of each test case contains two integers R and C (1 ≤ R, C ≤ 1000), the number of rows and the number of columns of the grid, respectively.

Each of the next R lines contains C integers between 1 and 10⁹, representing the values in the row.

For each test case, print the answer on a single line.

1
3 3
3 3 1
3 3 1
2 2 5

16