지뢰 제거

시간제한 1초

문제

---

N x N의 크기의 지도에 지뢰가 매설되어 있다. 지뢰는 1 x 1 크기를 차지하며, 아래와 같이 3가지 종류의 지뢰가 존재한다. 초기에는 지뢰가 매설되어 있기만 한 상태로 존재한다.

각 지뢰에는 번호가 적혀 있으며, 각 지뢰는 위의 그림과 같이 폭발한다. 색칠된 부분은 지뢰 폭발의 영향을 받는 부분이며, 이 부분은 그 잔해로 인해 땅이 새까맣게 타버린다. 만약 색칠된 부분에 지뢰가 있을 경우, 그 지뢰 또한 폭발하게 된다. 이제 이 지도에 최대 2발의 미사일을 쏘려 한다. 한 개의 미사일은 1 x 1 크기의 칸 한 개를 정확하게 폭발시켜 새까맣게 태울 수 있으며, 만약 해당 칸에 지뢰가 있을 경우 그 지뢰는 폭발하게 된다. 최대 2발의 미사일을 쏘아 최대한 지도 위의 많은 칸을 새까맣게 태우고 싶다고 할 때, (1) 그 새까맣게 태울 수 있는 칸의 최댓값과 (2) 해당 최댓값을 얻을 수 있도록 미사일을 발사할 수 있는 서로 다른 모든 경우의 수를 출력하는 프로그램을 작성하시오.

입력

---

첫 번째 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 10) 이후 각각의 테스트 케이스가 주어진다. 각 테스트케이스의 첫 번째 줄에는 지도의 세로 길이 N과 가로 길이 M이 주어진다. (1 ≤ N, M ≤ 15) 이후 N개의 줄에 대하여 지도의 정보가 주어진다. 각 줄은 M개의 숫자로 이루어져 있으며, 0은 지뢰 없음, 1은 1번 지뢰, 2는 2번 지뢰, 3은 3번 지뢰가 해당 칸에 존재함을 나타낸다.

출력

---

각 테스트케이스 별로 최대 2발의 미사일을 쏘아 새까맣게 태울 수 있는 칸의 갯수의 최댓값을 출력한다. 각 줄의 첫 번째 숫자는 테스트케이스의 번호이며, 두 번째 숫자는 칸의 갯수의 최댓값, 세 번째 숫자는 해당 최댓값을 얻을 수 있도록 미사일을 발사 할 수 있는 서로 다른 모든 경우의 수이다.

예제 입력

copy

3 3 3 0 0 3 0 1 0 0 0 0 5 5 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 7 7 2 0 0 1 0 0 0 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 0 0 2 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 2

예제 출력

copy

1 9 1 2 6 6 3 28 4