#P7884. Maximal submatrix

Maximal submatrix

Maximal submatrix

Problem Description

Given a matrix of n rows and m columns,find the largest area submatrix which is non decreasing on each column

Input

The first line contains an integer T(1≤T≤10)T(1 \leq T \leq 10)representing the number of test cases. For each test case, the first line contains two integers n,m(1≤n,m≤2∗103)n,m(1 \leq n,m \leq2*10^3) representing the size of the matrix the next n line followed. the i-th line contains mm integers vijv_{ij}(1≤vij≤5∗103)(1 \leq v_{ij} \leq 5*10^3)representing the value of matrix It is guaranteed that there are no more than 2 testcases with n∗m>10000n*m>10000

Output

For each test case, print a integer representing the Maximal submatrix

Sample Input

1

2 3

1 2 4

2 3 3

Sample Output

4

Source

2021“MINIEYE杯”中国大学生算法设计超级联赛(1)