Making Triangles with Matchsticks

You are given several matchsticks, all with the same length. Use all of them in the plane to form exactly one triangle.

A side of the triangle may be made by placing several matchsticks in a straight line. A matchstick may not be bent or cut to make part of a side.

Given the number of matchsticks, find how many distinct triangles can be made using every matchstick. Congruent triangles are counted as the same triangle.

With 9 matchsticks, there are 3 distinct triangles, as shown below.

Figure 1

Keep the following rules in mind.

1. Every given matchstick must be used, and exactly one triangle must be formed.
2. If no triangle can be formed, print 0. This happens when the number of matchsticks is 1, 2, or 4.
3. Congruent triangles are considered the same. For instance, the following two triangles made with 5 matchsticks are the same triangle.

Figure 2

The first line contains the number of matchsticks n.

1 <= n <= 50,000

Print the number of distinct triangles that can be made.