바람의 신

용태는 바람의 신이다.

용태는 구름을 움직여서 날씨를 조정할 수 있다. 구름의 밑에 있는 지역에는 항상 비가 내리며, 그 이외의 지역은 항상 맑다.

용태는 마음씨가 매우 좋기 때문에, 모든 마을에 비를 골고루 내리게 하려고 한다. 또, 축제나 시장이 열리는 날은 맑게 만들어 주려고 한다. 

용태가 맡은 나라는 창영제국이라는 매우 작은 나라이다. 이 나라는 4×4 크기의 정사각형으로 이루어져 있으며, 다음과 같이 번호가 매겨져 있다. 한 마을은 1×1 정사각형 하나를 차지한다.

구름의 크기는 2×2이며, 나라의 경계를 넘어갈 수 없다. 용태는 축제와 시장이 각 마을 별로 언제 열리는지를 알고 있다. 이 날은 그 마을에 비가 오면 안 된다.

첫 날에 구름은 이 나라의 중심부에 있다. (6-7-10-11)

그 다음 날 부터 하루가 시작하는 순간에 구름을 움직일 수 있다. 구름은 동서남북 중 한 방향으로 한 칸 또는 두 칸 움직일 수 있다. 구름을 전날과 같은 자리에 놔두는 것은 가능하다. 하지만, 대각선으로 움직이거나 서로 다른 방향으로 두 칸 움직이는 것은 불가능하다.

어떤 마을을 비가 오지 않은 채로 일주일을 내버려 두면 안 된다. 최대 6일까지 비가 오지 않은채로 있을 수 있지만, 적어도 7일이 되는 날에는 비가 와야 한다. 또, 문제가 시작하기 바로 전 날에는 모든 마을에 비가 왔고, N일 이후의 일은 전혀 관여할 필요가 없다.

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 마지막 줄에는 0이 하나 주어진다.

테스트 케이스의 첫째 줄에는 마지막 날 N이 주어진다. 다음 N개 줄에는 각 마을의 축제와 시장 계획이 주어진다. 한 줄에는 16개의 숫자가 주어지며, 1번마을부터 16번마까지 차례대로 주어진다. 1이면 축제나 시장이 열리는 것이고, 0이면 없는 것이다.

N은 365를 넘지 않는다.

각 테스트 케이스마다, 문제의 조건을 만족시키면서 비를 내리게 할 수 잇으면 1을, 없으면 0을 출력한다.