WONOWON - Wonowon


There is a little village in northern Canada called Wonowon, its name coming from the fact that it is located at Mile 101 of the Alaska Highway. While passing through this village, a wandering mathematician had an idea for a new type of number, which he called a wonowon number. He defined a wonowon number as a number whose decimal digits start and end with 1, and alternate between 0 and 1. Thus, the first four wonowon numbers are 101, 10101, 1010101, 101010101.

Neither 2 nor 5 can divide any wonowon number, but it is conjectured that every other prime number divides some wonowon number. For example, 3 divides 10101 (i.e. 3×3367), 7 divides 10101 (i.e. 7×1443), 11 divides 101010101010101010101 (i.e. 11 × 9182736455463728191).

Assume throughout that this conjecture is true, and let W(p) denote the number of digits in the smallest wonowon number divisible by p. Thus, for example, W(3) = 5, W(7) = 5, W(11) = 21, W(13) = 5, W(17) = 15, W(19) = 17.

It has been found experimentally that for many primes p, W(p) = p − 2 (as in the case for p = 7, 17, 19). Thus, your task is to write a program which reads an integer n and outputs the number of primes for which W(p) = p − 2. Note that p cannot be 2 nor 5, and p is a prime number less-than or equal to n.

Input

The input consists of a single integer 3 ≤ n ≤ 10000.

Output

The output should consist of a single integer representing the number of primes p for which W(p) = p − 2.

Example One

Input:
20

Output:
3

Example Two

Input:
100

Output:
14

hide comments
Piyush Kumar: 2016-06-21 08:59:54

I agree with Tjandra, the source code limit makes this question a bit easier than it actually is:)

(Tjandra Satria Gunawan)(曾毅昆): 2016-04-24 06:33:59

Easy one.. Could be more fun if source limit is < 300B..

darragh: 2016-03-31 11:38:09

@farhan764

"let W(p) denote the number of digits in the smallest wonowon number divisible by p."

Only the smallest wonowon number divisible by p matters.

farhan764: 2016-03-30 23:26:18

PS ....13 is also dividing 10101010101(11 digits)...so that 13 should be in counting....
according to me in example 1 ans should be 4.............

Vipul Srivastava: 2016-03-28 11:02:29

It is allowed but you should solve the problem without doing that.

Last edit: 2016-03-28 20:37:31
Ram: 2016-03-28 10:30:32

Can i pre compute the result and use it in my program ? That's not allowed right ?


Added by:Darragh Griffin
Date:2016-03-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
Resource:Irish Collegiate Programming Contest 2015 http://acm.ucc.ie/irlcpc