An equilateral triangle with side length $n$ can be divided into several smaller equilateral triangles with side length 1, which are called unit triangles. As shown in the figure, an equilateral triangle of side length 3 is divided into three layers containing a total of 9 unit triangles, which we number 1 to 9 from top to bottom and left to right. Similarly, an equilateral triangle of side length $n$ can be divided into $n^2$ unit triangles.

Four such equilateral triangles of side length $n$ can form a triangular pyramid. We label the three lateral faces of the triangular pyramid in clockwise order (viewed from the top to the bottom) as A, B, and C, and the base as D. The lateral faces A, B, and C have the apex of the pyramid as their top vertex, while the base face D has its intersection with faces A and B as its top vertex. The figure below shows the flattened plan of the triangular pyramid; the dots on each face indicate the top vertex of that face. In this figure, folding the lateral faces A, B, and C inward toward the paper restores the triangular pyramid. We divide each of these four faces A, B, C, and D into $n^2$ unit triangles.

Input data structure for faces A, B, C, and D

For any two unit triangles, if they share an edge, they are called adjacent unit triangles. Clearly, each unit triangle has three adjacent unit triangles. Now, randomly fill the total of $4n^2$ unit triangles across the four faces with the numbers $1 \sim 4n^2$.

You are required to write a program to find the maximum binary search tree (BST) formed by these unit triangles. A maximum binary search tree is defined as the tree with the most nodes among all binary search trees formed by the unit triangles. For any unit triangle, one of its three adjacent unit triangles can be chosen as its parent node, and the remaining two can be chosen as its left child and right child, respectively. Of course, the unit triangle chosen as the root node does not need a parent node, and for any node in the binary tree, the left and right children are not strictly required.

Input

The input file is tree.in. The first line contains an integer $n$ ($1 \le n \le 18$). The following $n^2$ lines each contain four integers, representing the values assigned to the unit triangles at the corresponding positions on faces A, B, C, and D, respectively.

Output

The output file is tree.out. It contains only one integer, representing the number of nodes in the maximum binary search tree.

Examples

Input 1

3
3 22 13 9
19 25 15 1
33 20 26 28
32 21 18 7
31 12 17 2
29 24 8 6
3 23 16 36
5 34 27 11
4 35 14 10

Output 1

17