MATRIX - Count maximum matrices

no tags 

You are given a matrix A of M rows and N columns, consisting of numbers 0 and 1. For a rectangle in A (sides >= 1), X1 is the number of ones on its sides, X0 is the number of zeros on its sides, and its value is defined as X1 – X0. Let us consider W, the maximum value taken over submatrices of A, and S, the number of submatrices with value W. Your task is to find W and S.

Input

The first line of input contains the number of testcases t (t <= 15). The first line of each testcase contains the numbers M, N (1 <= M, N <= 200) Then M lines follow. In each line, there are N numbers 0 or 1.

Output

For each testcase, you should output a single line with numbers W and S.

Example

Input:
1
5 6
1 1 1 1 1 1
1 0 0 0 0 1
1 0 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

Output:
18 1

hide comments
Raghavendran Ramachandran: 2012-10-09 17:50:46

Is a single row considered a rectangle?

Edit: Yes. (confirmed by AC)

Last edit: 2012-10-09 18:15:01
Walrus: 2012-02-09 04:10:27

What is side of a rectangle ?


Added by:Lê Đôn Khuê
Date:2005-06-08
Time limit:2.538s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET