#2777 바이러스

3 s   512 MB  

Description

N x N 격자판이 있다. 이 격자판의 한 칸은 비어있거나 바이러스가 있거나 벽이 있다. 바이러스는 매 시간 상, 하, 좌, 우 인접한 비어있는 칸으로 증식한다. 바이러스는 인접한 네 개의 칸이 모두 비어있지 않다면, 증식을 멈춘다. 당신은 벽과 바이러스가 배치되어 있는 격자판의 상태가 주어질 때, 정확히 3개의 비어있는 칸을 골라 벽을 설치 해야한다. 벽을 설치 한 후 바이러스가 증식하기 시작하고 모든 증식이 멈추었을 때 비어있는 칸의 갯수를 T라고 할때, 가장 큰 T는 얼마인가.

Input

가장 첫 줄에는 테스트 케이스의 갯수가 주어진다.

각 테스트 케이스는 첫 줄에 격자판의 크기 N 이 주어지고 다음 N 개의 행에 N 개의 정수가 주어진다.

0은 비어있는 칸을 1은 벽을 2는 바이러스를 의미한다.

 

테스트 케이스는 최대 100개 이고 격자판의 크기는 최대 10이다.

격자판 상의 바이러스는 항상 2개이다.

Output

각 테스트 케이스마다 문제에 대한 답을 한줄에 하나의 정수로 출력한다.

Sample Input

Sample Output

3
3
0 2 2
0 0 0
0 0 0
7
0 0 0 0 0 0 0
0 1 0 2 0 0 1
0 1 1 1 0 0 0
0 0 2 0 0 0 1
0 0 0 1 1 0 1
0 0 0 0 0 0 0
0 1 0 0 0 0 0
5
1 0 0 1 2
1 1 0 0 2
0 1 1 1 0
0 1 0 1 0
1 1 1 1 1
4
12
6

HINT

첫 번째 케이스의 경우

1 2 2

0 1 1

0 0 0

와 같이 벽을 설치해 4개의 빈칸을 얻을 수 있고 이 경우가 가장 많은 빈칸을 만드는 경우이다.