D. Beautiful Submatrices
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a prime number $$$p$$$ and a matrix $$$A$$$ of size $$$n \times m$$$. Rows are numbered from $$$1$$$ to $$$n$$$ and columns are numbered from $$$1$$$ to $$$m$$$. We will denote the element at the intersection of the $$$i$$$-th row and the $$$j$$$-th column as $$$a_{i,j}$$$. Every element of the array $$$A$$$ is an integer between $$$1$$$ and $$$p-1$$$.

We call a matrix beautiful if it satisfies the following condition:

  • $$$p$$$ divides the determinant of every non-trivial square submatrix of $$$A$$$.

Note that a matrix with no non-trivial square submatrix is beautiful.

A submatrix is defined by four integers $$$(i_1,j_1,i_2,j_2)$$$, where $$$1 \leq i_1 \leq i_2 \leq n \text{ and } 1 \leq j_1 \leq j_2 \leq m$$$, and consists of all elements $$$a_{i,j}$$$ of this matrix such that $$$i_1 \leq i \leq i_2$$$ and $$$j_1 \leq j \leq j_2$$$. A submatrix is called non-trivial if $$$i_1 \lt i_2$$$ and $$$j_1 \lt j_2$$$. A submatrix is called square if $$$i_2-i_1 = j_2-j_1$$$.

Find the number of submatrices of $$$A$$$ that are beautiful.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 1000$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$p$$$ ($$$1 \leq n,m \leq 1000$$$ and $$$2 \leq p \leq 10^9+7$$$)  — the number of rows of $$$A$$$, the number of columns of $$$A$$$, and the given prime number.

Then $$$n$$$ lines follow, describing the rows of $$$A$$$. Each of these lines contains $$$m$$$ integers $$$a_{i,1},a_{i,2},\dots,a_{i,m}$$$ ($$$1 \leq a_{i,j} \lt p$$$).

It is guaranteed that the sum over all tests of $$$n$$$ is not greater than $$$1000$$$.

Output

For each test case, output the number of beautiful submatrices of $$$A$$$.

Example
Input
2
4 4 1000000007
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
2 2 998244353
1 2
3 4
Output
100
8