God of Wind

Time limit1sMemory limit128 MB

Summary

Decide if a 2x2 cloud can move on a 4x4 grid, one to two cells per step in a straight line, so every village avoids rain-free streaks over 6 days while never raining on a marked village on its festival day.

Level: Medium6 of 10
Topics: BFS, Bit manipulation, Simulation
Solved: No attempts yet

Problem

Yongtae is the god of wind. He can control the weather by moving a cloud: it always rains on the area under the cloud, and everywhere else is always clear.

Yongtae is kind-hearted, so he wants to spread rain evenly over every village, and he wants to keep a village clear on the days it holds a festival or a market.

The country in Yongtae's charge, the Changyoung Empire, is a very small country shaped like a $4 \times 4$ square whose cells (villages) are numbered as shown below. Each village occupies one $1 \times 1$ cell.


1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

The cloud is $2 \times 2$ and may not go past the country's border. Yongtae knows when each village holds a festival or a market, and on those days that village must not get rain.

On the first day the cloud sits over the center of the country (villages 6, 7, 10, 11). Starting from the second day, at the moment a day begins he may move the cloud. The cloud may move one or two cells in a single direction (north, south, east, or west), or stay where it was the day before. It may not move diagonally, nor move two cells split across two different directions.

No village may be left without rain for a whole week. That is, a village may go without rain for at most 6 days, and on the day it would reach 7 days without rain it must get rain. On the day just before the problem starts, every village received rain, and anything that happens after day $N$ does not matter.

Given the festival and market schedule, write a program that decides whether it is possible to make it rain while satisfying all of the conditions.

Input

The input consists of several test cases, and the last line of the input contains a single $0$ .

The first line of each test case contains the last day $N$ ( $N$ does not exceed $365$ ). Each of the next $N$ lines gives that day's festival and market schedule as $16$ numbers, for villages $1$ through $16$ in order: $1$ means the village holds a festival or market that day, and $0$ means it does not.

Output

For each test case, print $1$ on its own line if it is possible to make it rain while satisfying all the conditions, and $0$ otherwise.

Examples1

Example 1

Input

1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
7
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1
0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0
0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0
7
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0
1 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0
0

Expected output