The Enchanted Vault#114

The Enchanted Vault

1 second

64 megabytes

Hard

An ancient mage hid treasures in a magical vault protected by an enchanted lock. The lock has three rotating disks, each marked with numbers from $1$ to $n$ . To open the lock, one must align the disks so that the sum of the three numbers is a prime number — for prime numbers possess special magical power.

A young wizard discovered this vault and wants to know how many different combinations he can try. Help him calculate the number of combinations of three numbers from $1$ to $n$ whose sum is a prime number.

Input

An integer $n$ ( $1 \leq n \leq 10000$ 1 \leq n \leq 10000).

Output

Output the number of combinations of three numbers from $1$ to $n$ such that their sum is a prime number.

Examples

Example 1

Loading

1 \leq n \leq 10000