write a go solution for F. Earnest Matrix Complementtime limit per test5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output3, 2, 1, ... We are the — RiOI Team!— Felix & All, Special Thanks 3 Peter: Good news: My problem T311013 is approved! delta: I'm glad my computer had gone out of battery so that I wouldn't have participated in wyrqwq's round and gained a negative delta. Felix: [thumbs_up] The problem statement concerning a removed song! Aquawave: Do I mourn my Chemistry? E.Space: ahh? Trine: Bread. Iris: So why am I always testing problems? Time will pass, and we might meet again. Looking back at the past, everybody has lived the life they wanted.Aquawave has a matrix A of size nxm, whose elements can only be integers in the range [1,k], inclusive. In the matrix, some cells are already filled with an integer, while the rest are currently not filled, denoted by -1.You are going to fill in all the unfilled places in A. After that, let c_u,i be the number of occurrences of element u in the i-th row. Aquawave defines the beauty of the matrix as\sum_{u=1}^k \sum_{i=1}^{n-1} c_{u,i} \cdot c_{u,i+1}.You have to find the maximum possible beauty of A after filling in the blanks optimally.InputThe first line of input contains a single integer t (1<=t<=2*10^4) — the number of test cases. The description of test cases follows.The first line of each test case contains three integers n, m, and k (2<=qn<=q2*10^5, 2<=m<=2*10^5, n*m<=6*10^5, 1<=k<=n*m) — the number of rows and columns of the matrix A, and the range of the integers in the matrix, respectively.Then n lines follow, the i-th line containing m integers A_i,1,A_i,2,ldots,A_i,m (1<=A_i,j<=k or A_i,j=-1) — the elements in A.It is guaranteed that the sum of n*m over all test cases does not exceed 6*10^5.OutputFor each test case, output a single integer — the maximum possible beauty.ExampleInput93 3 31 2 23 1 33 2 12 3 3-1 3 32 2 -13 3 6-1 -1 11 2 -1-1 -1 43 4 51 3 2 3-1 -1 2 -13 1 5 15 3 85 -1 21 8 -1-1 5 67 7 -14 4 46 6 5-1 -1 5 -1 -1 -1-1 -1 -1 -1 2 -1-1 1 3 3 -1 -1-1 1 -1 -1 -1 44 2 -1 -1 -1 4-1 -1 1 2 -1 -16 6 4-1 -1 -1 -1 1 -13 -1 2 2 4 -13 1 2 2 -1 -13 3 3 3 -1 2-1 3 3 -1 1 33 -1 2 2 3 -15 5 31 1 3 -1 12 2 -1 -1 3-1 -1 -1 2 -13 -1 -1 -1 2-1 1 2 3 -16 2 7-1 7-1 67 -1-1 -1-1 -12 2Output4
4
10
10
8
102
93
58
13
NoteIn the first test case, the matrix A is already determined. Its beauty is\sum_{u=1}^k \sum_{i=1}^{n-1} c_{u,i} \cdot c_{u,i+1} = c_{1,1}\cdot c_{1,2} + c_{1,2}\cdot c_{1,3} + c_{2,1}\cdot c_{2,2} + c_{2,2}\cdot c_{2,3} + c_{3,1}\cdot c_{3,2} + c_{3,2}\cdot c_{3,3} = 1\cdot 1 + 1\cdot 1 + 2\cdot 0 + 0\cdot 1 + 0\cdot 2 + 2\cdot 1 = 4.In the second test case, one can fill the matrix as follows: \begin{bmatrix} 2 &3 &3 \\ 2 &2 &3 \end{bmatrix}, and get the value 4. It can be proven this is the maximum possible answer one can get.In the third test case, one of the possible optimal configurations is: \begin{bmatrix} 1 &1 &1 \\ 1 &2 &1 \\ 1 &1 &4 \end{bmatrix}. In the fourth test case, one of the possible optimal configurations is: \begin{bmatrix} 1 &3 &2 &3 \\ 1 &3 &2 &1 \\ 3 &1 &5 &1 \end{bmatrix}. In the fifth test case, one of the possible optimal configurations is: \begin{bmatrix} 5 &5 &2 \\ 1 &8 &5 \\ 7 &5 &6 \\ 7 &7 &4 \\ 4 &4 &4 \end{bmatrix}. . Output only the code with no comments, explanation, or additional text.