Palindromic Primes

시간 제한12초메모리 제한1024 MB

요약

L 이상 H 이하의 정수 가운데 소수이면서 대칭수인 것의 개수를 센다. 두 경계는 10^12까지 커질 수 있다.

난이도: 보통10점 중 7점
유형: 수학, 정수론, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

A prime number is an integer greater than 1 which is only divisible by the integers 1 and itself, and no other positive integers. A palindromic number is one that is the same when read forwards or backwards, when written with no leading zeros. A palindromic prime is a prime number that is also a palindrome. The first few palindromic primes are 2, 3, 5, 7, 11 and 101.

Given two integers, L and H, determine the number of palindromic primes that are between L and H, inclusive.

입력

The first and only input line will contain two space separated integers: L (2 ≤ L ≤ 1012) and H (L ≤ H ≤ 1012), the lower and upper bounds (inclusive) for the search.

출력

Print a single integer on a line by itself: the number of palindromic primes between L and H, inclusive.

예제3

예제 1
입력
```
2 101
```
예상 출력
```
6
```
예제 2
입력
```
238 382
```
예상 출력
```
3
```
예제 3
입력
```
93139 97879
```
예상 출력
```
15
```