{"raw_statement":[{"iden":"statement","content":"You are given a grid $g$ consisting of $n$ rows each of which is divided into $m$ columns.\n\nYou can swap any two integers in the same row infinitely, but you cannot swap two integers from two different rows.\n\nYour 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, thin j$) ($1 < i <= n, thin 1 <= j <= m$) such that $g_{i , j}$ is equal to $g_{i -1 , j}$ (i.e. $g_{i , j} equiv g_{i -1 , j}$).\n\nThe first line contains an integer $T$ ($1 <= T <= 5$) specifying the number of test cases.\n\nThe first line of each test case contains two integers $n$ and $m$ ($1 <= n, m <= 10^3$), giving the number of rows and columns in the grid, respectively.\n\nThen $n$ lines follow, each line contains $m$ integers, giving the grid. All values in the grid are between $1$ and $10^8$ (inclusive). \n\nFor each test case, print a single line containing the beauty of the grid.\n\nAs 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.\n\n"},{"iden":"input","content":"The first line contains an integer $T$ ($1 <= T <= 5$) specifying the number of test cases.The first line of each test case contains two integers $n$ and $m$ ($1 <= n, m <= 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). "},{"iden":"output","content":"For each test case, print a single line containing the beauty of the grid."},{"iden":"note","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k, m_k \\in \\mathbb{Z} $ denote the number of rows and columns.  \n- Let $ G_k = (g_{k,i,j})_{1 \\le i \\le n_k, 1 \\le j \\le m_k} $ be the grid, where $ g_{k,i,j} \\in \\mathbb{Z} $ and $ 1 \\le g_{k,i,j} \\le 10^8 $.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 5 $  \n2. For each $ k \\in \\{1, \\dots, T\\} $:  \n   - $ 1 \\le n_k, m_k \\le 10^3 $  \n   - $ 1 \\le g_{k,i,j} \\le 10^8 $ for all $ i,j $  \n\n**Objective**  \nFor each test case $ k $, rearrange the elements within each row $ i $ arbitrarily (i.e., permute $ (g_{k,i,1}, \\dots, g_{k,i,m_k}) $).  \nMaximize the beauty:  \n$$\n\\sum_{i=2}^{n_k} \\sum_{j=1}^{m_k} \\mathbf{1}_{\\{g_{k,i,j} = g_{k,i-1,j}\\}}\n$$  \nOutput the maximum possible beauty.","simple_statement":"You are given an n×m grid. In each row, you can rearrange the numbers in any order. You cannot move numbers between rows.  \n\nThe beauty is the number of positions (i, j) where the number at row i, column j equals the number at row i-1, column j (for i from 2 to n).  \n\nMaximize the beauty by optimally rearranging each row.  \n\nPrint the maximum possible beauty.","has_page_source":false}