MATRIX - Đếm ma trận

Giới hạn
  • Thời gian: 2.538s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Cho ma trận A gồm M hàng, N cột, gồm các số 0 và 1.

Với 1 hình chữ nhật H nằm trong A với (cạnh >= 1), đặt X1 là số số 1 trên cạnh của H, X0 là số lượng số 0 nằm trên cạnh của H.

Giá trị của H được định nghĩa là X1 - X0.

Đặt W là giá trị lớn nhất của 1 hình chữ nhật nằm trong A.

Đặt S là số lượng hình chữ nhật nằm trong A và có giá trị là W.

Tìm W và S.

Input

Dòng đầu: t - số lượng test (t <= 15).

Mỗi test gồm:

  • Dòng đầu chứa 2 số M và N (1 <= M, N <= 200)
  • M dòng tiếp, mỗi dòng chứa N số 0 hoặc 1.

Output

Với mỗi test, in ra W và 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


  • Người up: beo_chay_so