울타리

준규는 화원을 운영한다. 값이 아주 비싼 꽃을 $R$행 $C$열의 땅에 심었는데 진욱이가 자꾸 훔쳐 가서 꽃밭 둘레를 울타리로 둘러쌌다. 그런데 시간이 지나면서 울타리 몇 군데가 부서졌고, 진욱이는 그 틈을 노려 다시 꽃을 훔치러 온다.

화원은 $R$행 $C$열 격자로 나타낸다. 0은 울타리가 없는 칸으로 꽃이 심겨 있을 수 있고, 1은 울타리가 서 있는 칸이다.

진욱이는 화원 바깥에서 출발한다. 격자의 가장 바깥 줄에 있는 칸이면 어디로든 들어올 수 있고, 안에서는 상하좌우 네 방향으로만 움직인다. 울타리 칸으로 들어가려면 그 울타리를 부숴야 하며, 부순 울타리 하나를 1회로 센다. 진욱이는 울타리를 부수지 않고 갈 수 있는 곳은 부수지 않고 가고, 부수지 않고는 더 들어갈 수 없을 때만 부순다.

그래서 칸마다 그 칸에 닿기까지 반드시 부숴야 하는 울타리의 최소 개수가 정해진다. 0인 칸 중에서 이 최소 개수가 가장 큰 값을 $D$라 하자. 울타리를 $D$번 부순 진욱이가 손에 넣는 꽃은 최소 개수가 정확히 $D$인 0인 칸이다. $D$와 그런 칸의 개수를 구하여라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다 ($T \le 10$).

각 테스트 케이스의 첫째 줄에는 두 정수 $R$과 $C$가 주어진다 ($5 \le R, C \le 1000$). $R$은 화원의 행 수이고 $C$는 열 수다.

이어지는 $R$개의 줄에는 화원의 정보가 한 줄에 $C$개씩 공백으로 구분되어 주어진다. 0은 꽃이 심길 수 있는 칸이고 1은 울타리가 있는 칸이다.

화원에는 0인 칸이 적어도 하나 있다.

각 테스트 케이스마다 두 정수를 한 줄에 출력한다. 첫 번째 정수는 진욱이가 부수는 울타리의 최대 개수 $D$이고, 두 번째 정수는 그때 얻는 꽃의 개수다. 두 정수는 공백으로 구분한다.

진욱이는 될 수 있으면 울타리를 부수지 않고 들어간다. 부수지 않고는 도저히 안으로 들어갈 수 없을 때만 울타리를 부순다.