Professor, I Want a Job

Seonggyu has high grades and is good at algorithms, so he competes in algorithm contests every year and brings home awards. His dream is to graduate in exactly four years, get hired at a good large company, and start earning money quickly.

One day Seonggyu went to the lecture hall for a major class, opened his book, and sat down. Before starting the lecture, the professor said a few words.

Professor: "Hmm... there is a student I have had my eye on... Yes, Seonggyu. How would you like to join my lab? Let us write a paper on algorithms together."

Seonggyu felt this was serious trouble. He wanted to graduate. Before he could think of an answer, the thought of running away came to him first!

The lecture hall has N rows across and N columns down, for N × N desks in total. The desk in the R-th row from the top and the C-th column from the left is written as (R, C). Each desk is either empty, occupied by a student other than Seonggyu, occupied by Seonggyu, or occupied by the professor.

To escape successfully, the distance between Seonggyu and the professor must be at least 5, and inside the axis-parallel rectangle whose two opposite corners are the professor and Seonggyu there must be at least three students other than Seonggyu who can hold the professor back.
However, if the professor and Seonggyu sit in the same row or the same column, there must be at least three students other than Seonggyu on the line segment connecting the professor and Seonggyu.

The distance between desk (a, b) and desk (c, d) is defined as $\sqrt{(a-c)^2 + (b-d)^2}$.

Seonggyu decides that being caught while running away is the worst outcome, so if there is no way to escape, he will quietly take the path of a graduate student. Write a program that tells Seonggyu whether he can definitely escape.

The first line of the input gives the natural number N (7 ≤ N ≤ 1,000).

From the second line, each of N lines gives N numbers, each one of 0, 1, 2, 5, separated by spaces.

If the C-th number on the R-th of the N lines is d, it means the following:

• d = 0: desk (R, C) is empty.
• d = 1: desk (R, C) is occupied by a student other than Seonggyu.
• d = 2: desk (R, C) is occupied by Seonggyu.
• d = 5: desk (R, C) is occupied by the professor.

Seonggyu and the professor do not overlap, and each of them sits in exactly one desk.

On the first line, print 1 if Seonggyu can escape from the professor, and 0 otherwise.