You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 1.0 s

Memory Limit: 128.0 MB

Description

Given an integer x, count the number of ordered triplets (a, b, c) of positive integers such that:

• a + b + c ≤ x.
• The sum (a + b + c) must be a prime number.
• Order matters (i.e., (1,1,2) ≠ (1,2,1)).
• Each of a, b, and c must be greater than 0.

Input

• A single integer x (1 ≤ x ≤ 1000).

Output

• Print a single integer — the number of valid triplets (a, b, c) that satisfy the conditions.

Sample

5

7

Explanation:
For x = 5, the valid ordered triplets where the sum is a prime number are:

• (1,1,1) → sum = 3 (prime)
• (1,1,3) → sum = 5 (prime)
• (1,2,2) → sum = 5 (prime)
• (1,3,1) → sum = 5 (prime)
• (2,1,2) → sum = 5 (prime)
• (2,2,1) → sum = 5 (prime)
• (3,1,1) → sum = 5 (prime)

Total valid triplets: 7