You are given an matrix M (consisting of nonnegative integers) and an integer K.  For any submatrix of M‘ of M define min(M‘) to be the minimum value of all the entries of M‘.  Now your task is simple:  find the maximum value of min(M‘) where M‘ is a submatrix of M of area at least K (where the area of a submatrix is equal to the number of rows times the number of columns it has).

Input

The first line contains a single integer T (T ≤ 10) denoting the number of test cases, T test cases follow.  Each test case starts with a line containing three integers, R (R ≤ 1000), C (C ≤ 1000) and K (K ≤ R * C) which represent the number of rows, columns of the matrix and the parameter K.  Then follow R lines each containing C nonnegative integers, representing the elements of the matrix M.  Each element of M is ≤ 10^9

Output

For each test case output two integers:  the maximum value of min(M‘), where M‘ is a submatrix of M of area at least K, and the maximum area of a submatrix which attains the maximum value of min(M‘).  Output a single space between the two integers.

Example

Input:22 2 21 11 13 3 21 2 34 5 67 8 9Output:1 48 2

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cmath>#include<string>#include<queue>#include<algorithm>#include<stack>#include<cstring>#include<vector>#include<list>#include<set>#include<map>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-14#define bug(x)  cout<<"bug"<<x<<endl;const int N=1e3+10,M=1e6+10,inf=2147483647;const ll INF=1e18+10,mod=1e9+7;int a[N][N],b[N][N];int l[N],r[N],s[N];int dp[N][N];int n,m,k;int check(int x){    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)        b[i][j]=(a[i][j]>=x);    memset(dp,0,sizeof(dp));    int ans=0;    for(int i=1;i<=n;i++)    {        for(int j=1;j<=m;j++)        if(b[i][j])dp[i][j]=dp[i-1][j]+1;        else dp[i][j]=0;        dp[i][0]=dp[i][m+1]=-1;        int si=0;        s[++si]=0;        for(int j=1;j<=n;j++)        {            while(dp[i][s[si]]>=dp[i][j])si--;            l[j]=s[si];            s[++si]=j;        }        si=0;        s[++si]=m+1;        for(int j=m;j>=1;j--)        {            while(dp[i][s[si]]>=dp[i][j])si--;            r[j]=s[si];            s[++si]=j;        }        for(int j=1;j<=m;j++)            ans=max(ans,(r[j]-l[j]-1)*dp[i][j]);    }    return ans;}int main(){    int T,cas=1;    scanf("%d",&T);    while(T--)    {        scanf("%d%d%d",&n,&m,&k);        for(int i=1;i<=n;i++)            for(int j=1;j<=m;j++)                scanf("%d",&a[i][j]);        int st=0;        int en=1e9+10,ans=-1;        while(st<=en)        {            int mid=(st+en)>>1;            if(check(mid)>=k)            {                ans=mid;                st=mid+1;            }            else                en=mid-1;        }        printf("%d %d\n",ans,check(ans));    }    return 0;}