405892: GYM102152 J Grid Beauty

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. Grid Beautytime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a grid $$$g$$$ consisting of $$$n$$$ rows each of which is divided into $$$m$$$ columns.

You can swap any two integers in the same row infinitely, but you cannot swap two integers from two different rows.

Your task is to maximize the beauty of the grid by rearranging integers in each row. The beauty of the grid is the number of pairs ($$$i,\,j$$$) ($$$1 < i \le n,\, 1 \le j \le m$$$) such that $$$g_{i,j}$$$ is equal to $$$g_{i-1,j}$$$ (i.e. $$$g_{i,j} \equiv g_{i - 1,j}$$$).

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 5$$$) specifying the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^3$$$), giving the number of rows and columns in the grid, respectively.

Then $$$n$$$ lines follow, each line contains $$$m$$$ integers, giving the grid. All values in the grid are between $$$1$$$ and $$$10^8$$$ (inclusive).

Output

For each test case, print a single line containing the beauty of the grid.

ExampleInput
2
2 3
1 2 3
4 1 2
3 3
5 7 9
3 2 9
5 3 2
Output
2
3
Note

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

加入题单

上一题 下一题 算法标签: