워노원 수

캐나다 북부에 워노원(Wonowon)이라는 작은 마을이 있다. 알래스카 하이웨이의 101마일 지점에 있어서 붙은 이름이다. 이 마을을 지나던 어느 수학자가 마을 이름을 딴 수를 정의했다. 워노원 수는 10진법으로 썼을 때 1로 시작해 1로 끝나고 1과 0이 번갈아 나오는 양의 정수다. 가장 작은 워노원 수 네 개는 101, 10101, 1010101, 101010101이다. 따라서 워노원 수의 자릿수는 항상 홀수이고 3 이상이다.

2와 5는 어떤 워노원 수도 나누지 못한다. 나머지 소수는 모두 어떤 워노원 수를 나눈다고 추측된다. 예를 들어 3은 10101을 나누고($3 \times 3367$), 7도 10101을 나누며($7 \times 1443$), 11은 101010101010101010101을 나눈다($11 \times 9182736455463728191$).

이 추측이 참이라고 하자. 소수 $p$로 나누어떨어지는 가장 작은 워노원 수의 자릿수를 $W(p)$라고 하면 $W(3) = 5$, $W(7) = 5$, $W(11) = 21$, $W(13) = 5$, $W(17) = 15$, $W(19) = 17$이다.

많은 소수에서 $W(p) = p - 2$가 성립한다는 사실을 실험으로 확인했다. 7, 17, 19가 그런 예다. 정수 $n$이 주어질 때, $p \le n$이고 2도 5도 아니며 $W(p) = p - 2$인 소수 $p$가 몇 개인지 구하라.

첫째 줄에 정수 $n$이 주어진다. ($3 \le n \le 10000$)

$p \le n$이고 2도 5도 아니며 $W(p) = p - 2$인 소수 $p$의 개수를 한 줄에 출력한다.