During the long-awaited summer vacation, to celebrate Xiao Bai's excellent performance in a math exam, Xiao Lan decided to take Xiao Bai on a trip.

After some deliberation, they decided to make Country T their destination. The territory of Country T can be represented by a convex $N$-sided polygon, where the $N$ vertices represent $N$ entry/exit points. Country T contains $N-2$ cities, each of which is a triangle whose vertices are vertices of the $N$-sided polygon (in other words, the cities form a triangulation of Country T). The travel route of the two can be viewed as a line segment connecting two non-adjacent vertices among the $N$ vertices.

To buy the best souvenirs, Xiao Bai hopes to pass through as many cities as possible on the travel route. As a friend of Xiao Lan, can you help them?

Input

Each input file contains only one test case.

The first line contains a single positive integer $N$, where $N$ is as described in the problem.

The next $N-2$ lines each contain three integers $p, q, r$, representing the indices of the three vertices of that city's triangle (the $N$ vertices of Country T are numbered from $1$ to $N$ in clockwise order).

Output

The output file contains a single line representing the maximum number of cities passed. (A city is considered passed if and only if it has at least two common points with the route.)

Examples

Input 1

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

Output 1

4

Constraints

For $20\%$ of the data, $N \le 2000$.

For $100\%$ of the data, $4 \le N \le 200000$.