정육면체 더미

위 그림은 정육면체를 쌓아 올린 더미를 비스듬히 본 모습이다. 1층에 8개, 2층에 4개, 3층에 1개가 놓여 있다. 이 더미를 위, 앞, 오른쪽에서 바라보면 아래 세 그림을 얻는다. 각각 위에서 본 그림, 앞에서 본 그림, 오른쪽에서 본 그림이라고 부르고, 세 그림 모두 더미를 돌리지 않고 본 모습이다.

거꾸로 세 그림이 주어지면 원래 더미의 모양을 짐작할 수 있다. 위, 앞, 오른쪽에서 본 모습이 서로 같은 더미는 여러 가지다.

세 그림과 똑같이 보이는 더미 중에서 정육면체를 가장 많이 쓴 더미가 몇 개를 쓰는지 구하는 프로그램을 작성하시오.

주어진 세 그림을 어떤 더미로도 만들지 못하는 경우도 있다. 또 이 더미는 중력이 작용하는 지구 위에 쌓으므로 모든 정육면체는 바닥이나 다른 정육면체 위에 놓인다. 세 그림이 실제로 만들 수 있는 모습인지도 판단해야 한다.

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

각 테스트 케이스의 첫째 줄에는 그림의 크기 $N$($1 \le N \le 300$)이 주어지고, 세 그림은 모두 $N \times N$이다. 이어지는 $3N$개의 줄에 위에서 본 그림, 앞에서 본 그림, 오른쪽에서 본 그림이 차례로 주어진다. 각 그림은 0과 1로 이루어진 $N \times N$ 행렬이고, 한 줄에 한 행씩, 원소는 공백 하나로 구분한다. 0은 그 자리에서 정육면체가 보이지 않는다는 뜻이고, 1은 보인다는 뜻이다.

행렬과 더미는 다음과 같이 대응한다. 바닥을 $N \times N$개의 칸으로 나누고, 행 번호는 뒤에서 앞으로 $1$부터 $N$까지, 열 번호는 왼쪽에서 오른쪽으로 $1$부터 $N$까지 매긴다. $(r, c)$ 칸에 쌓인 정육면체의 개수를 $h(r, c)$라고 하자.

• 위에서 본 그림의 $r$행 $c$열은 $h(r, c) > 0$일 때만 1이다.
• 앞에서 본 그림은 위쪽 행이 높은 층이어서 $k$행이 $N + 1 - k$층을 나타내고, $c$열은 왼쪽에서 $c$번째 바닥 열을 나타낸다. 그 열의 어느 한 칸이라도 정육면체가 $N + 1 - k$개 이상 쌓여 있으면 $k$행 $c$열이 1이다.
• 오른쪽에서 본 그림도 위쪽 행이 높은 층이다. 왼쪽에서 $m$번째 열은 앞에서 $m$번째 바닥 행, 즉 $N + 1 - m$행을 나타낸다. 그 행의 어느 한 칸이라도 정육면체가 $N + 1 - k$개 이상 쌓여 있으면 $k$행 $m$열이 1이다.

각 테스트 케이스마다 한 줄에 답을 출력한다. 세 그림과 똑같이 보이는 더미가 있으면 그런 더미에 쓰인 정육면체 개수의 최댓값을, 없으면 $-1$을 출력한다. 정육면체가 하나도 없는 빈 더미도 더미로 치므로, 세 그림이 모두 0으로만 이루어져 있으면 $0$을 출력한다.