TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

Little Olaf has two piggy banks. Every day he puts one Euro in one of the banks until each bank
contains N Euros. Then he can buy a new toy.


Little Olaf also likes prime numbers. Sometimes, the amount of Euros in the first bank concatenated
with the amount of Euros in the second bank is a prime number. For example, if the first bank contains
12 Euros and the second bank contains 7 Euros, the concatenation 127 is a prime number.


Your task is to find an optimal order to put the Euros in the banks so that as many prime numbers as
possible appear. Initially, each bank contains 1 Euro.


Here is one order to fill the banks when N = 4:



1, 1 -> 2, 1 -> 2, 2 -> 3, 2 -> 3, 3 -> 4, 3 -> 4, 4



Only one prime number appears: 43. The following order is much better:



1, 1 -> 2, 1 -> 3, 1 -> 4, 1 -> 4, 2 -> 4, 3 -> 4, 4



Now three prime numbers appear: 31, 41, and 43. This is an optimal filling order for N = 4.


Note that the initial 11 is not counted!

Input Format

The only line of input contains one integer N: the number of Euros that each piggy bank should
finally contain.


1 ≦ N ≦ 999

Output Format

The only line of output should contain one integer: the number of prime numbers in an optimal filling
order.

Sample Input 1

4
14
25

Sample Output 1

3
12
21

Hints

Problem Source

Migrated from old NTUJ.

BOI2011 Practice Day

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 200