Love Story VII

Time Limit: 3000 ms

Memory Limit: 65535 ms

Description

Xian Xu and Suzhen Bai met each other in a rainy day and fell in love at the first time. Although West Lake is very beautiful in rainy days, but it is not convenient for these ones who want have a date.
You are the God of Wind. By moving a big cloud around, you can decide the weather: it invariably rains under the cloud, and the sun shines everywhere else. But you are a benign God: your goal is to give enough rain to every field in the countryside, and sun to markets and festivals. To simplify this problem, this field is constituted of 4 x 4 square areas, denoted by their numbers (from 1 to 16 from left to right and from first line to the last). Your cloud is of size 2 x 2, and may not cross the borders of the country. You are given the schedule of the couples’ date time. On each of the following days, you may move your cloud by 1 or 2 squares in one of the four cardinal directions (North, West, South, and East), or leave it in the same position. Diagonal moves are not allowed. All moves occur at the beginning of the day. On the first day of the period, it is raining in the central areas (6-7-10-11), independently of the schedule.


You should not leave an area without rain for a full week (that is, you are allowed at most 6 consecutive days without rain). You don't have to care about rain on days outside the period you were given: i.e. you can assume it rains on the whole field the day before the period, and the day after it finishes.

Input

Input contains multiple test cases. A data set gives the number N of days (no more than 365) in the period on a single line, followed by N lines giving the schedule. The i-th line gives the schedule for the i-th day. It is composed of 16 numbers, either 0 or 1, 0 standing for a normal day, and 1 a date day. The field which is 1 cannot rain when you prepare it. The numbers are separated by one or more spaces.

Output

The answer is a 0 or 1 on a single line for each data set, 1 if you can satisfy the couple, 0 if there is no way to do it.

Sample Input

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

Sample Output

1

Hint

Source

方静远

提交代码