A number is special if the sum of its digits is a prime number. Given an integer \(N\), count the number of positive integer
pairs \((x, y)\) where both \(x\) and \(y\) are special and \(x + 2y = N\).

Input

• The first line of input contains the one integer \(N (1 \le N \le 10^{15})\).

Output

• Output a single number, the number of satisfied pairs.

Example

100

7