Given an integer N

N<=10^50

Print the no. of pairs (x,y) such that

0<=x<=n

0<=y<=n

F(x) +F(y) = Prime number

Where F(x) = sum of digits of x

Note : (x,y) and (y,x) are to be treated as same pair

First line consists of a single integer

Single consisting of a single integer

Example 1:

Input

3

Output

5

Example 2:

Input

5

Output

9

Example 3:

Input

10

Output

19

Login to see Discussion

Given a number n,

Maintain a set of pairs SET

Iterate i from 0 to n

Iterate j from 0 to n

Find if the sum of digits of i and sum of digits of j is a prime number

If the pair i,j is not present in SET,

Add it to SET

Finally print the number of sets in SET

**Note : **

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

Login to see Solution