Find all pairs of prime numbers (A, B) such that A<=B and their sum is also a prime number and does not exceed N.

Input

  The input of the problem consists of the only integer N (1<=N<=10^6).

Output      

On the first line of the output file write the number of pairs meeting the requirements.

Samples