Polygon

Memory limit: 32 MB

We say that two triangles intersect if their interiors have at least one common point. A polygon is called convex if every segment connecting any two of its points is contained in this polygon. A triangle whose vertices are also vertices of a convex polygon is called an elementary triangle of this polygon. A triangulation of a convex polygon is a set of elementary triangles of this polygon, such that no two triangles from the set intersect and a union of all triangles covers the polygon.

We are given a polygon and its triangulation. What is the maximal number of triangles in this triangulation that can be intersected by an elementary triangle of this polygon?

Example

Consider the following triangulation:

The elementary triangle intersects all the triangles in this triangulation.

Task

Write a program that:

• reads the number of vertices of a polygon and its triangulation from the standard input;
• computes the maximal number of triangles intersected by an elementary triangle of the given polygon;
• writes the result to the standard output.

Input

In the first line of the standard input there is a number , , which equals the number of vertices of the polygon. The vertices of the polygon are numbered from to clockwise.

The following lines describe the triangles in the triangulation. There are three integers separated by single spaces in the -st line, where . These are the numbers of the vertices of the -th triangle in the triangulation.

Output

In the first and only line of the standard output there should be exactly one integer — the maximal number of triangles in the triangulation, that can be intersected by a single elementary triangle of the input polygon.

Example

For the input data:

6
0 1 2
2 4 3
4 2 0
0 5 4

the correct result is:

4

Task author: Krzysztof Diks.