A prime number is an integer greater than $1$ that has no positive divisors other than $1$ and itself.

We call a number megaprime if it is prime and all of its individual digits are prime. For example, $53$ is megaprime because it is prime and all its digits ($5$ and $3$) are prime; however, $35$ is not megaprime because it is not prime (it's divisible by $5$ and $7$), and $13$ is not megaprime because it has a non-prime digit ($1$ is not prime).

Given two long integers, $first$ and $last$, find and print the total number of megaprime numbers in the inclusive range between $first$ and $last$.

Input Format

Two space-separated long integers describing the respective values of $first$ and $last$.

Constraints

$1\leq first\leq last\leq10^{15}$
$last-first\leq10^9$

Output Format

Print a long integer denoting the total number of megaprimes in the inclusive interval between $first$ and $last$.

Sample Input 0
1 100

Sample Output 0
8

Explanation 0

There are eight megaprime numbers in the inclusive range from $first=1$ to $last=100$ (i.e., $2$, $3$, $5$, $7$, $23$, $37$, $53$, and $73$), so we print $8$ as our answer.

Source: hackerrank | Difficulty: MEDIUM
Tags: Number theory


Solutions:
def getNextDigit(d):
	if d < 2:
		return 2
	if d < 3:
		return 3
	if d < 5:
		return 5
	if d < 7:
		return 7
	return None

def getNumbersBetween(first, last):
	first_ = tuple(map(int, str(first)))
	number = [2] * len(first_)
	i = 0
	while i < len(first_) and first_[i] in {2, 3, 5, 7}:
		number[i] = first_[i]
		i += 1
	if i < len(first_):
		number[i] = getNextDigit(first_[i] - 1)
		if number[i] == None:
			number[i] = 2
			i -= 1
			report = True
			while report == True and i >= 0:
				number[i] = getNextDigit(number[i])
				report = number[i] == None
				if report:
					number[i] = 2
				i -= 1
			if report:
				number = [2] + number
	while True:
		number_ = int(''.join(map(str, number)))
		if number_ > last:
			return
		yield number_
		(i, report) = (len(number) - 1, True)
		while report == True and i >= 0:
			number[i] = getNextDigit(number[i])
			report = number[i] == None
			if report:
				number[i] = 2
			i -= 1
		if report:
			number = [2] + number

def isProbablePrime(n, ar=None):
	if n <= 1:
		return False
	if n == 2:
		return True
	if n % 2 == 0:
		return False
	if n < 9:
		return True
	if n % 3 == 0:
		return False
	if n % 5 == 0:
		return False
	if not ar:
		if n < 1373653:
			ar = (2, 3)
		elif n < 9080191:
			ar = (31, 73)
		elif n < 4759123141:
			ar = (2, 7, 61)
		elif n < 2152302898747:
			ar = (2, 3, 5, 7, 11)
		elif n < 3474749660383:
			ar = (2, 3, 5, 7, 11, 13)
		else:
			ar = (2, 3, 5, 7, 11, 13, 17)
	for a in ar:
		if a == n:
			continue
		(t, u) = (0, n - 1)
		while u & 1 == 0:
			t += 1
			u >>= 1
		xi1 = pow(a, u, n)
		for i in range(0, t):
			xi2 = xi1 * xi1 % n
			if xi2 == 1 and xi1 != 1 and (xi1 != n - 1):
				return False
			xi1 = xi2
		if xi1 != 1:
			return False
	return True
(first, last) = map(int, input().split())
print(sum((1 for n in getNumbersBetween(first, last) if isProbablePrime(n))))


import sys

def rep(j):
	return (2 * pow(10, j) - 1) // 9

def valid(d):
	if d == 2 or d == 3:
		return 1
	if d == 5 or d == 7:
		return 1
	return 0

def primetest(n):
	if n == 1:
		return 0
	lim = 20
	if n < lim:
		lim = int(n)
	for i in range(2, lim):
		if pow(i, n - 1, n) != 1:
			return 0
	return 1

def succ(term):
	temp = term
	j = 0
	while temp % 10 == 7:
		temp = temp // 10
		j = j + 1
	d = temp % 10
	if d == 2:
		return (temp + 1) * pow(10, j) + rep(j)
	if d == 3:
		return (temp + 2) * pow(10, j) + rep(j)
	if d == 5:
		return (temp + 2) * pow(10, j) + rep(j)
	return rep(j + 1)

def legal(first):
	digits = []
	for i in range(20):
		digits.append(0)
	temp = first
	len = 1
	while temp > 9:
		temp = temp // 10
		len = len + 1
	temp = first
	for i in range(1, len + 1):
		d = temp % 10
		temp = temp // 10
		digits[len - i] = d
	answer = 0
	for j in range(len):
		d = digits[j]
		if valid(d) == 1:
			answer = 10 * answer + d
		elif d < 7:
			while valid(d) == 0:
				d = d + 1
			answer = 10 * answer + d
			return answer * pow(10, len - 1 - j) + rep(len - j - 1)
		else:
			answer = succ(answer)
			return answer * pow(10, len - j) + rep(len - j)
	return answer
(first, last) = input().strip().split(' ')
(first, last) = [int(first), int(last)]
term = legal(first)
count = 0
while term <= last:
	if primetest(term) == 1:
		count = count + 1
	term = succ(term)
print(count)


__author__ = 'Ward'
import sys
from random import randrange

def is_prime(n, k=10):
	if n == 2 or n == 3:
		return True
	if not n & 1:
		return False

	def check(a, s, d, n):
		x = pow(a, d, n)
		if x == 1:
			return True
		for i in range(s - 1):
			if x == n - 1:
				return True
			x = pow(x, 2, n)
		return x == n - 1
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for i in range(k):
		a = randrange(2, n - 1)
		if not check(a, s, d, n):
			return False
	return True

def isPrimeDigit(a):
	return a == '2' or a == '3' or a == '5' or (a == '7')

def findNext(a):
	if a == 0:
		return 2
	if a % 10 == 2:
		return a + 1
	if a % 10 == 3 or a % 10 == 5:
		return a + 2
	else:
		return findNext(a // 10) * 10 + 2

def findFirst(a):
	ans = 0
	x = False
	for digit in str(a):
		if x:
			ans = ans * 10 + 2
		elif isPrimeDigit(digit):
			ans = ans * 10 + int(digit)
		else:
			if digit == '0' or digit == '1':
				ans = ans * 10 + 2
			if digit == '4':
				ans = ans * 10 + 5
			if digit == '6':
				ans = ans * 10 + 7
			if digit == '8' or digit == '9':
				ans = findNext(ans) * 10 + 2
			x = True
	return ans
(First, Last) = map(int, sys.stdin.readline().split())
A = findFirst(First)
Answer = 0
while A <= Last:
	if is_prime(A):
		Answer += 1
	A = findNext(A)
print(Answer)


import sys
import re

def _try_composite(a, d, n, s):
	if pow(a, d, n) == 1:
		return False
	for i in range(s):
		if pow(a, 2 ** i * d, n) == n - 1:
			return False
	return True

def is_prime(n, _precision_for_huge_n=16):
	if n in _known_primes or n in (0, 1):
		return True
	if any((n % p == 0 for p in _known_primes)):
		return False
	(d, s) = (n - 1, 0)
	while not d % 2:
		(d, s) = (d >> 1, s + 1)
	if n < 1373653:
		return not any((_try_composite(a, d, n, s) for a in (2, 3)))
	if n < 25326001:
		return not any((_try_composite(a, d, n, s) for a in (2, 3, 5)))
	if n < 118670087467:
		if n == 3215031751:
			return False
		return not any((_try_composite(a, d, n, s) for a in (2, 3, 5, 7)))
	if n < 2152302898747:
		return not any((_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11)))
	if n < 3474749660383:
		return not any((_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13)))
	if n < 341550071728321:
		return not any((_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17)))
	return not any((_try_composite(a, d, n, s) for a in _known_primes[:_precision_for_huge_n]))
_known_primes = [2, 3]
_known_primes += [x for x in range(5, 1000, 2) if is_prime(x)]

def mrtest(n, k=5):
	from random import randint
	if n < 2:
		return False
	for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]:
		if n % p == 0:
			return n == p
	(s, d) = (0, n - 1)
	while d % 2 == 0:
		(s, d) = (s + 1, d // 2)
	for i in range(k):
		x = pow(randint(2, n - 1), d, n)
		if x == 1 or x == n - 1:
			continue
		for r in range(1, s):
			x = x * x % n
			if x == 1:
				return False
			if x == n - 1:
				break
		else:
			return False
	return True
(first, last) = input().strip().split(' ')
(first, last) = [int(first), int(last)]

def run2(first, last):
	r = re.compile('^[2357]*$')
	count = 0
	if first <= 2 and last >= 2:
		count += 1
	if first <= 3 and last >= 3:
		count += 1
	if first <= 5 and last >= 5:
		count += 1
	if first < 7:
		first = 7
	if first % 2 == 0:
		first += 1
	d0 = first % 10
	if d0 == 1:
		first += 2
	elif d0 == 5:
		first += 2
	elif d0 == 9:
		first += 4
	d0 = first % 10
	adder = 0
	if d0 == 3:
		adder = 4
	elif d0 == 7:
		adder = 6
	n = first
	while n <= last:
		sn = str(n)
		if re.match(r, sn) is not None:
			if is_prime(n):
				count += 1
			n += adder
			adder = 4 if adder == 6 else 6
		else:
			for (ninc, c) in enumerate(sn[:-1]):
				if c not in '2357':
					toadd = 10 ** (len(sn) - 1 - ninc)
					n += 10 ** (len(sn) - 1 - ninc)
					n -= n % toadd
					n += 3
					adder = 4
					break
			else:
				n += adder
				adder = 4 if adder == 6 else 6
	return count
print(run2(first, last))


import sys
import math
mega_ones = [3, 7]
mega_digits = [2, 3, 5, 7]

class mega_dig:

	def __init__(self, low, high):
		self.lo = low
		self.hi = high
		self.state = None
		self.initialise()

	def __iter__(self):
		return self

	def mega_index(self, num, tiny):
		digits = mega_digits
		if tiny:
			digits = mega_ones
		for (index, meg) in enumerate(digits):
			if meg >= num:
				return (index, False, meg > num)
		return (0, True, False)

	def initialise(self):
		cand = str(self.lo)
		self.state = [0] * len(cand)
		carry = False
		for (rev_index, digit) in enumerate(cand):
			index = len(cand) - 1 - rev_index
			num = int(digit)
			tiny = False
			if index == 0 and len(cand) > 1:
				tiny = True
			(mega, carry, stop) = self.mega_index(num, tiny)
			self.state[index] = mega
			if carry:
				index += 1
				while index < len(cand):
					self.state[index] = (self.state[index] + 1) % 4
					if self.state[index] != 0:
						break
					index += 1
				if index == len(cand):
					self.state.append(0)
				stop = True
			if stop:
				break

	def increment(self):
		for index in range(len(self.state)):
			mod = 4
			if index == 0 and len(self.state) > 1:
				mod = 2
			self.state[index] = (self.state[index] + 1) % mod
			if self.state[index] != 0:
				break
			if index == len(self.state) - 1:
				self.state.append(0)

	def get_num(self):
		if len(self.state) == 1:
			return mega_digits[self.state[0]]
		res_array = [0] * len(self.state)
		for index in range(1, len(self.state)):
			res_array[index] = str(mega_digits[self.state[index]])
		res_array[0] = str(mega_ones[self.state[0]])
		res = ''.join(list(reversed(res_array)))
		return int(res)

	def __next__(self):
		num = self.get_num()
		if num <= self.hi:
			self.increment()
			return num
		else:
			raise StopIteration()

def _try_composite(a, d, n, s):
	if pow(a, d, n) == 1:
		return False
	for i in range(s):
		if pow(a, 2 ** i * d, n) == n - 1:
			return False
	return True

def is_prime_rose(n, _precision_for_huge_n=16):
	if n in _known_primes or n in (0, 1):
		return True
	if any((n % p == 0 for p in _known_primes)):
		return False
	(d, s) = (n - 1, 0)
	while not d % 2:
		(d, s) = (d >> 1, s + 1)
	if n < 1373653:
		return not any((_try_composite(a, d, n, s) for a in (2, 3)))
	if n < 25326001:
		return not any((_try_composite(a, d, n, s) for a in (2, 3, 5)))
	if n < 118670087467:
		if n == 3215031751:
			return False
		return not any((_try_composite(a, d, n, s) for a in (2, 3, 5, 7)))
	if n < 2152302898747:
		return not any((_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11)))
	if n < 3474749660383:
		return not any((_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13)))
	if n < 341550071728321:
		return not any((_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17)))
	return not any((_try_composite(a, d, n, s) for a in _known_primes[:_precision_for_huge_n]))
_known_primes = [2, 3]
_known_primes += [x for x in range(5, 1000, 2) if is_prime_rose(x)]

def mega_in_range(first, last):
	count = 0
	for num in mega_dig(first, last):
		if is_prime_rose(num):
			count += 1
	return count

def solve(in_file, out_file):
	(first, last) = (int(raw) for raw in in_file.readline().strip().split(' '))
	out_file.write('{}\n'.format(mega_in_range(first, last)))
from_file = False
if from_file:
	path = 'Data\\'
	name = 'mega_prime'
	file_input = open(path + name + '.in', 'r')
	file_output = open(path + name + '.out', 'w')
	solve(file_input, file_output)
	file_input.close()
	file_output.close()
else:
	solve(sys.stdin, sys.stdout)


import sys
import math
import random

def init(x, valids):
	sp = list(str(x))
	found = False
	for (idx, el) in enumerate(sp):
		if el not in valids:
			for i in range(idx + 1, len(sp)):
				sp[i] = '2'
			break
	sp = sp[::-1]
	carret = False
	for (idx, el) in enumerate(sp):
		if carret:
			if el == '9':
				sp[idx] = '0'
				el = sp[idx]
				carret = True
			else:
				sp[idx] = chr(ord(sp[idx]) + 1)
				el = sp[idx]
				carret = False
		if el not in valids:
			if el > '7':
				carret = True
				sp[idx] = '2'
			else:
				for vel in valids:
					if vel > el:
						sp[idx] = vel
						break
	if carret:
		sp.append('2')
	sp = sp[::-1]
	return int(''.join(sp))

def pprime(p):
	if p == 2:
		return True
	if not p & 1:
		return False
	sol = True
	for i in range(32):
		a = random.randint(1, p - 1)
		sol = sol and pow(a, p - 1, p) == 1
		if sol is False:
			return False
	return True

def prime(p):
	if p == 2:
		return True
	if not p & 1:
		return False
	return pow(2, p - 1, p) == 1
(first, last) = input().strip().split(' ')
(first, last) = [int(first), int(last)]
counter = 0
primes = ['2', '3', '5', '7']
first = init(first, primes)
pointer = first
while pointer <= last:
	if prime(pointer) and pprime(pointer):
		counter += 1
	pointer = init(pointer + 1, primes)
print(counter)


import sys
powers2 = [1] * 55
for i in range(1, 55):
	powers2[i] = 2 * powers2[i - 1]
witness = [2, 3, 5, 7, 11, 13, 17, 19, 23]
known_p = set([2, 3]) | set(witness)

def isprime(n):
	if n in known_p:
		return True
	if n <= 1 or any((n % p == 0 for p in known_p)):
		return False
	d = n - 1
	s = 0
	while d % 2 == 0:
		d //= 2
		s += 1
	for a in witness:
		if pow(a, d, n) == 1:
			continue
		couldbep = False
		for r in range(s):
			if pow(a, powers2[r] * d, n) == n - 1:
				couldbep = True
				continue
		if couldbep:
			continue
		return False
	return True
powers = [1] * 20
for i in range(1, 20):
	powers[i] = 10 * powers[i - 1]

def pick(n, ind):
	n //= powers[ind]
	return n % 10
allowed = set([2, 3, 5, 7])
not_allowed = set([4, 6, 8])
corr = {0: 2, 1: 1, 2: 0, 3: 0, 4: 1, 5: 0, 6: 1, 7: 0, 8: 4, 9: 3}

def clos(X):
	ind = -1
	tmp = X
	while tmp > 0:
		tmp //= 10
		ind += 1
	while ind >= 0 and pick(X, ind) in allowed:
		ind -= 1
	if ind == -1:
		return X
	X //= powers[ind]
	X *= powers[ind]
	for i in range(ind):
		X += 2 * powers[i]
	need_count = pick(X, ind) > 7
	X += corr[pick(X, ind)] * powers[ind]
	if need_count:
		ind += 1
		left = X // powers[ind]
		cutted_numb = left - 10 * (left // 10)
		while cutted_numb in not_allowed:
			X += corr[cutted_numb] * powers[ind]
			ind += 1
			left = X // powers[ind]
			cutted_numb = left - 10 * (left // 10)
	return X
not_allowed = set([1, 4, 6, 8])
corr = {0: 2, 1: 1, 2: 0, 3: 0, 4: 1, 5: 0, 6: 1, 7: 0, 8: 4, 9: 3}

def plus1(X):
	X += 1
	ind = 0
	left = X
	cutted_numb = left - 10 * (left // 10)
	while left > 0 and cutted_numb in not_allowed:
		X += corr[cutted_numb] * powers[ind]
		ind += 1
		left = X // powers[ind]
		cutted_numb = left - 10 * (left // 10)
	return X
(first, last) = input().strip().split(' ')
(first, last) = [int(first), int(last)]
numb = clos(first)
count = 0
while numb <= last:
	if isprime(numb):
		count += 1
	numb = plus1(numb)
print(count)


import sys, bisect
(first, last) = input().strip().split(' ')
(first, last) = [int(first), int(last)]
pr = [2]
for n in range(3, 100, 2):
	for p in pr:
		if n % p == 0:
			break
		if p * p > n:
			pr.append(n)
			break

def Miller_Rabin_composite_test(a, d, n):
	if pow(a, d, n) == 1:
		return 0
	while d < n:
		if pow(a, d, n) == n - 1:
			return 0
		d *= 2
	return 1

def Miller_Rabin_prime(n):
	d = (n - 1) // 2
	while d % 2 == 0:
		d //= 2
	for a in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
		if Miller_Rabin_composite_test(a, d, n):
			return 0
	return 1

def isprime(n):
	if n <= pr[-1]:
		i = bisect.bisect_left(pr, n)
		return pr[i] == n
	for p in pr:
		if n % p == 0:
			return 0
		if p * p > n:
			return 1
	return Miller_Rabin_prime(n)

def gen1(first, last):
	if first == 0:
		yield 0
		first = 2
	if last < first:
		return
	for t in gen1(first // 10, last // 10):
		for i in [2, 3, 5, 7]:
			y = 10 * t + i
			if first <= y and y <= last:
				yield y

def gen(first, last):
	for t in gen1(first // 10, last // 10):
		for i in [3, 7]:
			y = 10 * t + i
			if first <= y and y <= last:
				yield y
ans = 0
while first < 10 and first <= last:
	ans += isprime(first)
	first += 1
for i in gen(first, last):
	ans += isprime(i)
print(ans)


import sys

def miller_rabin_pass(a, s, d, n):
	a_to_power = pow(a, d, n)
	if a_to_power == 1:
		return True
	for i in range(s - 1):
		if a_to_power == n - 1:
			return True
		a_to_power = a_to_power * a_to_power % n
	return a_to_power == n - 1

def miller_rabin(n):
	if n < 2:
		return False
	if n in {2, 3, 5, 7, 11, 13, 17, 19, 23}:
		return True
	d = n - 1
	s = 0
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in {2, 3, 5, 7, 11, 13, 17, 19, 23}:
		if not miller_rabin_pass(a, s, d, n):
			return False
	return True
(first, last) = input().strip().split(' ')
(first, last) = [int(first), int(last)]
s = set()
s.add('2')
s.add('3')
s.add('5')
s.add('7')
if last <= 22222:
	m = first % 10
	j = (3 - m) % 10
	k = (7 - m) % 10
	count = 0
	for i in range(first + k, last + 1, 10):
		if set(str(i)).issubset(s):
			if miller_rabin(i):
				count += 1
	for i in range(first + j, last + 1, 10):
		if set(str(i)).issubset(s):
			if miller_rabin(i):
				count += 1
	if first <= 5 and last >= 5:
		count += 1
	if first <= 2 and last >= 2:
		count += 1
else:
	m = first % 100000
	b = [23, 27, 33, 37, 53, 57, 73, 77]
	c = []
	for i1 in {2, 3, 5, 7}:
		for i2 in {2, 3, 5, 7}:
			for i3 in {2, 3, 5, 7}:
				for j in b:
					c.append(int(str(i1) + str(i2) + str(i3) + str(j)))
	a = []
	for i in c:
		a.append((i - m) % 100000)
	count = 0
	for i in range(max(1, first), min(22221, last) + 1):
		if set(str(i)).issubset(s):
			if miller_rabin(i):
				count += 1
	for i in range(512):
		for j in range(first + a[i], last + 1, 100000):
			if set(str(j)).issubset(s):
				if miller_rabin(j):
					count += 1
print(count)


from itertools import product
import random

def miller_rabin(N, k):
	d = N - 1
	r = 0
	while d % 2 == 0:
		d //= 2
		r += 1
	for _ in range(k):
		a = random.randint(2, N - 2)
		x = pow(a, d, N)
		if x == 1 or x == N - 1:
			continue
		flag = False
		for _ in range(r - 1):
			x = x * x % N
			if x == 1:
				return False
			if x == N - 1:
				flag = True
				break
		else:
			return False
	else:
		return True

def suffs(n):
	a = ['2357'] * (n - 1) + ['37']
	return {int(''.join(s)) for s in product(*a)}

def valid(n):
	for c in str(n):
		if c not in {'2', '3', '5', '7'}:
			return False
	return True
(first, last) = [int(x) for x in input().split()]
q = first // 10 ** 9
numbers = set()
for k in range(2, 10):
	numbers |= suffs(k)
numbers |= {q * 10 ** 9 + s for s in suffs(9)}
numbers |= {(q + 1) * 10 ** 9 + s for s in suffs(9)}
numbers = {x for x in numbers if first <= x <= last and valid(x)}
print(sum((miller_rabin(x, 25) for x in numbers)) + len([x for x in {2, 3, 5, 7} if first <= x <= last]))


def is_prime(n):
	if n < 6:
		return [False, False, True, True, False, True][n]
	elif n & 1 == 0:
		return False
	else:
		(s, d) = (0, n - 1)
		while d & 1 == 0:
			(s, d) = (s + 1, d >> 1)
		for a in filter(lambda x: x < n, [2, 3, 5, 7, 11, 13, 17]):
			x = pow(a, d, n)
			if x != 1 and x + 1 != n:
				for r in range(1, s):
					x = pow(x, 2, n)
					if x == 1:
						return False
					elif x == n - 1:
						a = 0
						break
				if a:
					return False
		return True

def round_down(x, i):
	if i == len(x):
		return
	if x[i] in {'1', '0'}:
		x[i + 1:] = ['7'] * (len(x) - i - 1)
	elif x[i] in {'9', '8', '6', '4'}:
		x[i] = {'9': '7', '8': '7', '6': '5', '4': '3'}[x[i]]
		x[i + 1:] = ['7'] * (len(x) - i - 1)
	else:
		lenx = len(x)
		round_down(x, i + 1)
		if len(x) == lenx - 1:
			x[i] = {'7': '5', '5': '3', '3': '2', '2': '7'}[x[i]]
			if x[i] in {'5', '3', '2'}:
				x.append('7')
	return

def round_up(x):
	if not x:
		return x
	if x[0] == '9' or x[0] == '8':
		return ['2'] * (len(x) + 1)
	elif x[0] == '6':
		return ['7'] + ['2'] * (len(x) - 1)
	elif x[0] == '4':
		return ['5'] + ['2'] * (len(x) - 1)
	elif x[0] == '1' or x[0] == '0':
		return ['2'] * len(x)
	else:
		lower = round_up(x[1:])
		if len(lower) == len(x) - 1:
			return [x[0]] + lower
		elif x[0] == '7':
			return ['2'] * (len(x) + 1)
		elif x[0] == '5':
			return ['7'] + ['2'] * (len(x) - 1)
		elif x[0] == '3':
			return ['5'] + ['2'] * (len(x) - 1)
		elif x[0] == '2':
			return ['3'] + ['2'] * (len(x) - 1)

def increment(x):
	if len(x) == 1:
		if x[0] == '2':
			return ['3']
		elif x[0] == '3':
			return ['5']
		elif x[0] == '5':
			return ['7']
		else:
			return ['2', '2']
	lower = increment(x[1:])
	if len(lower) == len(x) - 1:
		return [x[0]] + lower
	elif x[0] == '7':
		return ['2'] * (len(x) + 1)
	elif x[0] == '5':
		return ['7'] + ['2'] * (len(x) - 1)
	elif x[0] == '3':
		return ['5'] + ['2'] * (len(x) - 1)
	elif x[0] == '2':
		return ['3'] + ['2'] * (len(x) - 1)
(first, last) = input().strip().split()
(first, last) = (list(first), list(last))
first = round_up(first)
round_down(last, 0)
megaprimes = 0
while len(first) < len(last) or (len(first) == len(last) and first <= last):
	num = int(''.join(first))
	if is_prime(num):
		megaprimes += 1
	first = increment(first)
print(megaprimes)


import sys
(first, last) = input().strip().split(' ')
MapUp = {0: 2, 1: 2, 2: 2, 3: 3, 4: 5, 5: 5, 6: 7, 7: 7, 8: None, 9: None, None: None}
Primes = {2, 3, 5, 7}

def IncUp(Split, Inc=0):
	Split[-1] += Inc
	Split = [0] + Split
	for i1 in range(1, len(Split)):
		if Split[i1] not in Primes:
			for i2 in range(i1, 0, -1):
				if Split[i2] == 8 or Split[i2] == 9 or Split[i2] == 10:
					Split[i2] = 2
					Split[i2 - 1] += 1
				else:
					Split[i2] = MapUp[Split[i2]]
			if Split[0] != 0:
				Split[0] = MapUp[Split[0]]
			if i1 != len(Split) - 1:
				for i2 in range(i1 + 1, len(Split)):
					Split[i2] = 2
			break
	if Split[0] == 0:
		Split = Split[1:]
	return Split
first = str(int(first))
FirstSplit = IncUp([int(m) for m in first])
FirstActual = ''.join([str(m) for m in FirstSplit])

def MillerRabin(a, d, n, s):
	if pow(a, d, n) == 1:
		return True
	for i in range(s):
		if pow(a, 2 ** i * d, n) == n - 1:
			return True
	return False

def IsPrime(n):
	if n == 2 or n == 3 or n == 5 or (n == 7):
		return True
	elif n % 2 == 0:
		return False
	(d, s) = (n - 1, 0)
	while not d % 2:
		(d, s) = (d >> 1, s + 1)
	for a in (2, 3, 5, 7, 11, 13, 17):
		if not MillerRabin(a, d, n, s):
			return False
	if n < 341550071728321:
		return True
	elif n == 341550071728321:
		return False
	else:
		return True
PowerMemo = {}

def ListToInt(Split):
	n = len(Split)
	if n in PowerMemo:
		PowTen = PowerMemo[n]
	else:
		PowTen = [10 ** m for m in range(n)]
		PowTen.reverse()
		PowerMemo[n] = PowTen
	Out = 0
	for i1 in range(n):
		Out += PowTen[i1] * Split[i1]
	return Out
CurrentActual = [m for m in FirstSplit]
CurrentInt = int(FirstActual)
LastInt = int(last)
Count = 0
if CurrentInt > LastInt:
	print(0)
else:
	while CurrentInt <= LastInt:
		Prime = IsPrime(CurrentInt)
		if Prime:
			Count += 1
		CurrentActual = IncUp(CurrentActual, 1)
		CurrentInt = ListToInt(CurrentActual)
	print(Count)


import sys
import math
import random

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	while k > 0:
		a = 2 + int(random.random() * n) % (n - 4)
		if pow(a, n - 1, n) != 1:
			return False
		k -= 1
	return True

def nextMega(num):
	if num < 10:
		if num <= 1:
			return 2
		elif num == 2:
			return 3
		elif num <= 4:
			return 5
		elif num <= 6:
			return 7
		else:
			return 23
	else:
		lastdigit = num % 10
		if lastdigit < 3:
			return num + 3 - lastdigit
		elif lastdigit < 7:
			return num + 7 - lastdigit
		else:
			return nextMega3(num + 3 - lastdigit, 1)

def getDigit(num, i):
	return num % 10 ** (i + 1) // 10 ** i

def nextDigit(num):
	if num <= 1:
		return 2
	elif num == 2:
		return 3
	elif num <= 4:
		return 5
	elif num <= 6:
		return 7
	else:
		return 2

def nextMega3(num, i):
	digit = getDigit(num, i)
	newdigit = nextDigit(digit)
	newnum = num + (newdigit - digit) * 10 ** i
	if newdigit > digit:
		return newnum
	else:
		return nextMega3(newnum, i + 1)
(first, last) = input().strip().split(' ')
(first, last) = [int(first), int(last)]
k = 10
count = 0
nonprimedigits = set({0, 1, 4, 6, 8, 9})
firsts = list(str(first))
for i in range(len(firsts)):
	d = int(firsts[i])
	if d in nonprimedigits:
		for j in range(i + 1, len(firsts)):
			firsts[j] = '2'
		newd = nextDigit(d)
		firsts[i] = str(newd)
		while newd < d:
			if i == 0:
				firsts.insert(0, '2')
				break
			i -= 1
			d = int(firsts[i])
			newd = nextDigit(d)
			firsts[i] = str(newd)
		break
num = int(''.join(firsts))
while num <= last:
	if isPrime(num, k):
		count += 1
	num = nextMega(num)
print(count)


def test(a, d, n, s):
	if pow(a, d, n) == 1:
		return False
	for i in range(s):
		if pow(a, 2 ** i * d, n) == n - 1:
			return False
	return True
P = set((2, 3, 5, 7, 11, 13, 17, 19, 23))

def prime(n):
	if n in P:
		return True
	(d, s) = (n - 1, 0)
	while d & 1 == 0:
		(d, s) = (d >> 1, s + 1)
	return not any((test(a, d, n, s) for a in P))

def dig(n):
	d = []
	while n:
		(n, r) = divmod(n, 10)
		d.append(r)
	return d

def dig4(n, l):
	D = [2, 3, 5, 7]
	X = []
	for i in range(l):
		(n, r) = divmod(n, 4)
		X.append(r)
	X.reverse()
	m = 0
	for r in X:
		m = 10 * m + D[r]
	return m

def bracket(n):
	(m, c, f) = (0, 0, 0)
	X = dig(n)
	X.reverse()
	l = len(X)
	D = [0, 0, 0, 1, 1, 2, 2, 3, 3, 3]
	C = [-1, -1, 0, 0, 1, 0, 1, 0, 1, 1]
	R = []
	for i in X:
		if c != 0:
			d = f
		else:
			d = D[i]
			c = C[i]
			if c:
				f = 0 if d == 0 else 3
		m = 4 * m + d
	(m0, l0) = (m, l)
	if c == 1:
		m += 1
		if m > 4 ** l - 1:
			m = 0
			l += 1
		return ((m0, l0), (m, l))
	if c == -1:
		m -= 1
		if m < 0:
			l -= 1
			m = 4 ** l - 1
		return ((m, l), (m0, l0))
	return ((m, l), (m, l))
(a, b) = map(int, input().split())
((x, y), (m0, l0)) = bracket(a)
((m1, l1), (x, y)) = bracket(b)
N = 0
for l in range(l0, l1 + 1):
	M = 4 ** l if l < l1 else m1 + 1
	for m in range(m0, M):
		n = dig4(m, l)
		if prime(n):
			N += 1
	m0 = 0
print(N)


import sys
from bisect import bisect_right
(first, last) = input().strip().split(' ')
(first, last) = [int(first), int(last)]

def isPrime(n, k=5):
	from random import randint
	if n < 2:
		return False
	for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]:
		if n % p == 0:
			return n == p
	(s, d) = (0, n - 1)
	while d % 2 == 0:
		(s, d) = (s + 1, d // 2)
	for i in range(k):
		x = pow(randint(2, n - 1), d, n)
		if x == 1 or x == n - 1:
			continue
		for r in range(1, s):
			x = x * x % n
			if x == 1:
				return False
			if x == n - 1:
				break
		else:
			return False
	return True
prime_digits = ['2', '3', '5', '7']
next_idx = {'2': 1, '3': 2, '5': 3}

def first_allp_leq(num):
	result = str(num)
	if len(result) == 1:
		if result in prime_digits:
			return int(result)
		elif result < '7':
			return int(prime_digits[bisect_right(prime_digits, result)])
	if result[-1] < '3':
		result = result[:-1] + '3'
	if result[0] > '7':
		return int('2' * len(result) + '3')
	else:
		i = 0
		while i < len(result) and result[i] in prime_digits:
			i += 1
		if i == len(result):
			return int(result)
		elif bisect_right(prime_digits, result[i]) < len(prime_digits):
			if i == len(result) - 1:
				return int(result[:i] + max(prime_digits[bisect_right(prime_digits, result[i])], '3'))
			else:
				return int(result[:i] + prime_digits[bisect_right(prime_digits, result[i])] + '2' * (len(result) - i - 2) + '3')
		else:
			j = i - 1
			while j >= 0 and result[j] >= '7':
				j -= 1
			if j < 0:
				return int('2' * len(result) + '3')
			return int(result[:j] + prime_digits[bisect_right(prime_digits, result[j])] + '2' * (len(result) - j - 2) + '3')
next_idx = {'2': 1, '3': 2, '5': 3}

def next_num(num, mod_pos):
	result = str(num)
	if mod_pos == -1:
		return (int('2' * len(result) + '3'), len(result))
	if len(result) == 1:
		new_num = int(prime_digits[next_idx[result]])
		if new_num == 7:
			return (new_num, -1)
		else:
			return (new_num, 0)
	if mod_pos == len(result) - 1:
		if result[mod_pos] == '2':
			return (int(result[:i] + '3'), mod_pos)
		else:
			result = result[:mod_pos] + '7'
			mod_pos -= 1
			while mod_pos >= 0 and result[mod_pos] == '7':
				mod_pos -= 1
			return (int(result), mod_pos)
	else:
		return (int(result[:mod_pos] + prime_digits[next_idx[result[mod_pos]]] + '2' * (len(result) - mod_pos - 2) + '3'), len(result) - 1)

def megaprimes_btw(first, last):
	result = 0
	cur_num = int(first_allp_leq(first))
	st_cur_num = str(cur_num)
	mod_pos = len(st_cur_num) - 1
	while mod_pos >= 0 and st_cur_num[mod_pos] == '7':
		mod_pos -= 1
	while cur_num <= last:
		if isPrime(cur_num):
			result += 1
		(cur_num, mod_pos) = next_num(cur_num, mod_pos)
	return result
print(megaprimes_btw(first, last))


from math import floor, log10, ceil
import itertools

def miller_rabin(n):
	if n < 2:
		return False
	if n == 2:
		return True
	if n == 3:
		return True
	if n & 1 == 0:
		return False
	witness = [2, 3, 5, 7, 11, 13, 17, 19]
	r = 0
	d = n - 1
	while d & 1 == 0:
		d >>= 1
		r += 1
	for a in [w for w in witness if w <= n - 2]:
		x = pow(a, d, n)
		if x == 1 or x == n - 1:
			continue
		for i in range(r):
			x = pow(x, 2, n)
			if x == 1:
				return False
			if x == n - 1:
				break
		else:
			return False
	return True
(first, last) = [int(x) for x in input().split()]
P = [10 ** i for i in range(20)]

def gd(x, n):
	return x // P[n] % 10
nudge = [2, 1, 1, 2, 1, 2, 1, 5, 4, 3]
valid = {2, 3, 5, 7}
twos = [0, 2, 22, 222, 2222, 22222, 222222, 2222222, 22222222, 222222222, 2222222222, 22222222222, 222222222222, 2222222222222, 22222222222222, 222222222222222]

def getnext(n):
	nd = 0
	tmp = n
	while tmp > 0:
		tmp //= 10
		nd += 1
	i = nd - 1
	while i >= 0:
		d = gd(n, i)
		if d not in valid:
			if d < 7:
				n += P[i] * nudge[d]
				n = n // P[i] * P[i] + twos[i]
				break
			else:
				n = n // P[i + 1] * P[i + 1] + twos[i + 1]
				carry = True
				while carry:
					i += 1
					d = gd(n, i)
					carry = d >= 7
					n += P[i] * nudge[d]
				break
		i -= 1
	return n

def tick(n):
	carry = True
	i = 0
	d = gd(n, i)
	n += P[i] * nudge[d]
	if n > 9:
		while carry:
			i += 1
			d = gd(n, i)
			if d in valid:
				break
			n += P[i] * nudge[d]
			carry = d >= 7
	return n
n = getnext(first)
cnt = 0
while n <= last:
	if miller_rabin(n):
		cnt += 1
	n = tick(n)
print(cnt)


import sys

def miller_rabin2(p, a):
	d = p - 1
	s = 0
	while d & 1 == 0:
		d = d >> 1
		s += 1
	r = pow(a, d, p)
	if r == 1 or r == p - 1:
		return True
	for _ in range(s - 1):
		r = r * r % p
		if r == p - 1:
			return True
	return False

def miller_rabin(p):
	for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
		if a >= p:
			return True
		if not miller_rabin2(p, a):
			return False
	return True

def mega_range(first, last):
	nxt = {0: 2, 1: 1, 2: 0, 3: 0, 4: 1, 5: 0, 6: 1, 7: 0, 8: 4, 9: 3}
	powers10 = [10 ** i for i in range(20)]
	last_digit = {3, 7}
	x = first
	for mag in reversed(powers10):
		if mag > x:
			continue
		inc = nxt[x // mag % 10]
		if inc:
			x += mag * inc
			mag = mag // 10
			while mag:
				x = x - x % (mag * 10) + mag + mag
				mag = mag // 10
	while x <= last:
		if x % 10 in last_digit or x < 10:
			yield x
		x += 1
		for mag in powers10:
			if mag > x:
				break
			x += mag * nxt[x // mag % 10]
(first, last) = [int(x) for x in input().split()]
count = 0
for i in mega_range(first, last):
	if miller_rabin(i):
		count += 1
print(count)


import sys

def megaprimes(first, last):
	ans = 0
	firstdigs = [int(c) for c in str(first)]
	lastdigs = [int(c) for c in str(last)]
	while len(firstdigs) < len(lastdigs):
		ans += mprec(firstdigs, None, -len(firstdigs), 0)
		firstdigs = [0] + firstdigs
	sofar = 0
	for (i, (fdig, ldig)) in enumerate(zip(firstdigs, lastdigs)):
		if fdig == ldig:
			if fdig not in {2, 3, 5, 7}:
				return 0
			sofar = 10 * sofar + fdig
			continue
		k = i
		ans += mprec(firstdigs, lastdigs, i - len(firstdigs), sofar)
		return ans

def mprec(firstdigs, lastdigs, negind, sofar):
	if negind == 0:
		return 1 if isprime(sofar) else 0
	ans = 0
	for digit in (2, 3, 5, 7):
		(firstdigs1, lastdigs1) = (firstdigs, lastdigs)
		if firstdigs:
			fdig = firstdigs[negind]
			if fdig > digit:
				continue
			if fdig < digit:
				firstdigs1 = None
		if lastdigs:
			ldig = lastdigs[negind]
			if ldig < digit:
				break
			if ldig > digit:
				lastdigs1 = None
		ans += mprec(firstdigs1, lastdigs1, negind + 1, 10 * sofar + digit)
	return ans

def isprime(num, witnesses=(2, 3, 5, 7, 11, 13, 17, 19, 23)):
	(s, d) = (0, num - 1)
	while d & 1 == 0:
		d >>= 1
		s += 1
	for witness in witnesses:
		if witness == num:
			return True
		wtod = pow(witness, d, num)
		if wtod == 1 or wtod == num - 1:
			continue
		for r in range(1, s):
			wtod = wtod * wtod % num
			if wtod == num - 1:
				break
		else:
			return False
	return True
(first, last) = input().strip().split(' ')
(first, last) = [int(first), int(last)]
print(megaprimes(first, last))


import sys
(a, b) = (int(x) for x in input().split())
import random
_mrpt_num_trials = 5

def is_probable_prime(n):
	assert n >= 2
	if n == 2:
		return True
	if n % 2 == 0:
		return False
	s = 0
	d = n - 1
	while True:
		(quotient, remainder) = divmod(d, 2)
		if remainder == 1:
			break
		s += 1
		d = quotient
	assert 2 ** s * d == n - 1

	def try_composite(a):
		if pow(a, d, n) == 1:
			return False
		for i in range(s):
			if pow(a, 2 ** i * d, n) == n - 1:
				return False
		return True
	for i in range(_mrpt_num_trials):
		a = random.randrange(2, n)
		if try_composite(a):
			return False
	return True

def digits(x):
	rv = 0
	adder = 1
	while x > 0:
		t = x % 10
		if t != 2 and t != 3 and (t != 5) and (t != 7):
			rv = adder
		x = x // 10
		adder *= 10
	return rv
foo = 222222222222222
count = 0
x = a
while x <= b:
	add = digits(x)
	if add > 0:
		x -= x % add
		x += foo % add
		x += add
		continue
	if is_probable_prime(x):
		count += 1
	x += 1
print(count)


import sys
import itertools
from collections import defaultdict
primelist = []
primes = defaultdict(int)

def rwh_primes2(n):
	correction = n % 6 > 1
	n = {0: n, 1: n - 1, 2: n + 4, 3: n + 3, 4: n + 2, 5: n + 1}[n % 6]
	sieve = [True] * (n // 3)
	sieve[0] = False
	for i in range(int(n ** 0.5) // 3 + 1):
		if sieve[i]:
			k = 3 * i + 1 | 1
			sieve[k * k // 3::2 * k] = [False] * ((n // 6 - k * k // 6 - 1) // k + 1)
			sieve[(k * k + 4 * k - 2 * k * (i & 1)) // 3::2 * k] = [False] * ((n // 6 - (k * k + 4 * k - 2 * k * (i & 1)) // 6 - 1) // k + 1)
	return [2, 3] + [3 * i + 1 | 1 for i in range(1, n // 3 - correction) if sieve[i]]
primelist = rwh_primes2(10000000)
for x in primelist:
	primes[x] = 1

def MillerRabin(n):
	if n == 0 or n == 1 or n == 4 or (n == 6) or (n == 8) or (n == 9):
		return False
	if n == 2 or n == 3 or n == 5 or (n == 7):
		return True
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	assert 2 ** s * d == n - 1

	def trial_composite(a):
		if pow(a, d, n) == 1:
			return False
		for i in range(s):
			if pow(a, 2 ** i * d, n) == n - 1:
				return False
		return True
	for a in {2, 3, 5, 7, 11, 13, 17}:
		if trial_composite(a):
			return False
	return True

def Primality(n):
	if primes[n] == 1:
		return True
	for x in primelist:
		if n % x == 0:
			return False
	return MillerRabin(n)
digits = [2, 3, 5, 7]
digitstr = ['2', '3', '5', '7']
(first, last) = input().strip().split(' ')
(first, last) = [int(first), int(last)]
s = str(first)
t = str(last)
minLen = len(s)
maxLen = len(t)
count = 0
classes = [3, 7]
for i in range(1, 6):
	temp = []
	for x in classes:
		for d in digits:
			temp.append(d * 10 ** i + x)
	classes = temp
classes.sort()
m = first % 10 ** 6
for x in classes:
	if m <= x:
		num = first + (x - m)
	else:
		num = first + (10 ** 6 - m + x)
	while num <= last:
		a = str(num)
		if all((b in digitstr for b in a)):
			if MillerRabin(num):
				count += 1
		num += 10 ** 6
if first < 10 ** 6:
	for l in range(minLen, 6):
		values = itertools.product(digitstr, repeat=l)
		for x in values:
			if l > 1 and (x[l - 1] == 5 or x[l - 1] == 2):
				continue
			num = int(''.join(x))
			if num > last:
				break
			if num >= first:
				if Primality(num):
					count += 1
print(count)


import sys
import math
(first, last) = input().strip().split(' ')
(first, last) = [int(first), int(last)]
size = int(min(10000000, last) ** 0.5) + 1

def isPrime(n):
	if n < 2:
		return False
	elif n == n or n == 3:
		return True
	else:
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				return False
		return True

def sieveToPrimeList(sieve):
	pList = []
	for (index, value) in enumerate(sieve):
		if value:
			pList += [index]
	return pList

def primes(n):
	sieve = [True] * (n + 1)
	if len(sieve) < 2:
		return []
	else:
		sieve[0] = False
		sieve[1] = False
	for i in range(2, int(len(sieve) ** 0.5) + 1):
		if sieve[i] == False:
			continue
		elif isPrime(i):
			sieve[i] = True
			for j in range(2 * i, len(sieve), i):
				sieve[j] = False
		else:
			sieve[i] = False
	s = sieveToPrimeList(sieve)
	return s
primeList = primes(size)
primeSet = set(primeList)

def legendre(a, m):
	return pow(a, m - 1 >> 1, m)

def is_sprp(n, b=2):
	d = n - 1
	s = 0
	while d & 1 == 0:
		s += 1
		d >>= 1
	x = pow(b, d, n)
	if x == 1 or x == n - 1:
		return True
	for r in range(1, s):
		x = x * x % n
		if x == 1:
			return False
		elif x == n - 1:
			return True
	return False

def is_lucas_prp(n, D):
	P = 1
	Q = 1 - D >> 2
	s = n + 1
	r = 0
	while s & 1 == 0:
		r += 1
		s >>= 1
	t = 0
	while s > 0:
		if s & 1:
			t += 1
			s -= 1
		else:
			t <<= 1
			s >>= 1
	U = 0
	V = 2
	q = 1
	inv_2 = n + 1 >> 1
	while t > 0:
		if t & 1 == 1:
			(U, V) = ((U + V) * inv_2 % n, (D * U + V) * inv_2 % n)
			q = q * Q % n
			t -= 1
		else:
			(U, V) = (U * V % n, (V * V - 2 * q) % n)
			q = q * q % n
			t >>= 1
	while r > 0:
		(U, V) = (U * V % n, (V * V - 2 * q) % n)
		q = q * q % n
		r -= 1
	return U == 0

def is_prime(n):
	if n < size:
		return n in primeSet
	for p in primeSet:
		if n % p == 0:
			return False
	if not is_sprp(n):
		return False
	a = 5
	s = 2
	while legendre(a, n) != n - 1:
		s = -s
		a = s - a
	return is_lucas_prp(n, a)

def isPrimeByList(n):
	m = n ** 0.5 + 1
	for p in primeList:
		if p > m:
			break
		if n % p == 0:
			return False
	return True

def addOne(n):
	if not n:
		return '2'
	if n[-1] == '2':
		return n[:-1] + '3'
	elif n[-1] == '3':
		return n[:-1] + '5'
	elif n[-1] == '5':
		return n[:-1] + '7'
	else:
		return addOne(n[:-1]) + '2'

def getFirst(start):
	s = str(start)
	n = ''
	done = False
	while not done and s:
		if s[0] < '2':
			done = True
			n += '2' * len(s)
		elif s[0] == '2':
			n += '2'
			s = s[1:]
		elif s[0] < '3':
			done = True
			n += '3' + '2' * (len(s) - 1)
		elif s[0] == '3':
			n += '3'
			s = s[1:]
		elif s[0] < '5':
			done = True
			n += '5' + '2' * (len(s) - 1)
		elif s[0] == '5':
			n += '5'
			s = s[1:]
		elif s[0] < '7':
			done = True
			n += '7' + '2' * (len(s) - 1)
		elif s[0] == '7':
			n += '7'
			s = s[1:]
		else:
			done = True
			if n:
				n = addOne(n) + '2' * len(s)
			else:
				n = '7' + '2' * len(s)
	return int(n)
count = 0
nextValue = getFirst(first)
while nextValue <= last:
	if nextValue == 2 or is_prime(nextValue):
		count += 1
	nextValue = int(addOne(str(nextValue)))
print(count)


import sys
import math
import random
import itertools
(first, last) = input().strip().split(' ')
(first, last) = [int(first), int(last)]
digits = [2, 3, 5, 7]

def digit_map(x):
	rest = x
	level = 0
	rval = 0
	while rest > 0:
		digit = digits[(rest - 1) % 4]
		rval = rval + digit * 10 ** level
		rest = (rest - 1) // 4
		level = level + 1
	return rval

def find_closest(x):
	i = 1
	while digit_map(i) < x:
		i = i * 2
	left = i // 2
	right = i
	while left < right:
		mid = (left + right) // 2
		if digit_map(mid) == x:
			return mid
		elif digit_map(mid) < x:
			if digit_map(mid + 1) > x:
				return mid
			left = mid
		elif digit_map(mid) > x:
			right = mid
	return left

def generate_digits(min_number, max_number):
	i = find_closest(min_number)
	x = digit_map(i)
	while x < max_number:
		if x > min_number:
			yield x
		i += 1
		x = digit_map(i)

def candidates(min_candidate, max_candidate):
	return generate_digits(min_candidate, max_candidate)

def is_prime(n):
	if n == 1:
		return False
	if n == 2:
		return True
	if n % 2 == 0:
		return False
	d = (n - 1) // 2
	r = 1
	while d % 2 == 0 and d != 1:
		d = d // 2
		r += 1
	k = 20
	for _ in range(k):
		a = random.randint(2, n - 1)
		x = pow(a, d, n)
		if x == 1 or x == n - 1:
			continue
		for i in range(r - 1):
			x = pow(x, 2, n)
			if x == 1:
				return False
			if x == n - 1:
				break
		if x == n - 1:
			continue
		return False
	return True
print(len([i for i in candidates(first, last) if is_prime(i)]))


import sys
import random
(first, last) = tuple((int(x) for x in sys.stdin.readline().split()))
k = 10

def factorize(n):
	assert n > 0
	r = 0
	while n & 1 == 0:
		r += 1
		n >>= 1
	return (n, r)
assert factorize(3) == (3, 0)
assert factorize(14) == (7, 1)
assert factorize(16) == (1, 4)

def is_prime(n, k):
	assert n > 0
	if n == 1:
		return False
	if n < 4:
		return True
	(d, r) = factorize(n - 1)
	for _ in range(k):
		a = random.randint(2, n - 2)
		x = pow(a, d, n)
		if x == 1 or x == n - 1:
			continue
		for _ in range(r - 1):
			x = pow(x, 2, n)
			if x == 1:
				return False
			if x == n - 1:
				break
		else:
			return False
		continue
	return True

class Meganum:

	def __init__(self, digits=[2]):
		for d in digits:
			assert d in (2, 3, 5, 7)
		self.digits = digits

	def increment(self, rank=0):
		if rank == len(self.digits):
			self.digits.append(2)
		elif self.digits[rank] == 2:
			self.digits[rank] = 3
		elif self.digits[rank] == 3:
			self.digits[rank] = 5
		elif self.digits[rank] == 5:
			self.digits[rank] = 7
		elif self.digits[rank] == 7:
			self.digits[rank] = 2
			self.increment(rank + 1)

	def skip(self):
		if len(self.digits) > 1 and self.digits[0] in (2, 5):
			self.increment()

	def integer(self):
		total = 0
		multiplier = 1
		for d in self.digits:
			total += d * multiplier
			multiplier *= 10
		return total

	@staticmethod
	def from_integer(n):
		digits = []
		while n > 0:
			(n, r) = divmod(n, 10)
			digits.append(r)
		i = 0
		while i < len(digits):
			if digits[i] < 2:
				digits[i] = 2
				for j in range(i):
					digits[j] = 2
			elif digits[i] == 4:
				digits[i] = 5
				for j in range(i):
					digits[j] = 2
			elif digits[i] == 6:
				digits[i] = 7
				for j in range(i):
					digits[j] = 2
			elif digits[i] > 7:
				digits[i] = 2
				for j in range(i):
					digits[j] = 2
				if i == len(digits) - 1:
					digits.append(0)
				digits[i + 1] += 1
			i += 1
		return Meganum(digits)
counter = 0
mn = Meganum.from_integer(first)
mn.skip()
n = mn.integer()
while n <= last:
	if n >= first and is_prime(n, k):
		counter += 1
	mn.increment()
	mn.skip()
	n = mn.integer()
print(counter)


small_trailing = [i and max((int(not i % 2 ** j) and j for j in range(1, 8))) for i in range(256)]

def trailing(n):
	low_byte = n & 255
	if low_byte:
		return small_trailing[low_byte]
	res = 0
	while not n & 1:
		n //= 2
		res += 1
	return res

def Fermat_test(n, base, s, t):
	b = pow(base, t, n)
	if b == 1 or b == n - 1:
		return True
	else:
		for j in range(1, s):
			b = pow(b, 2, n)
			if b == n - 1:
				return True
			if b == 1:
				return False
	return False

def isprime(n, bases=[336781006125, 9639812373923155]):
	s = trailing(n - 1)
	t = n >> s
	for base in bases:
		if not Fermat_test(n, base, s, t):
			return False
	return True

def ls2num(ls):
	res = 0
	for c in ls:
		res = 10 * res + ord(c) - 48
	return res

def promoteN1(ls, i):
	if i < 0:
		ls.insert(0, '2')
	elif ls[i] > '7':
		ls[i] = '2'
		promoteN1(ls, i - 1)
	else:
		ls[i] = {'0': '2', '1': '2', '2': '3', '3': '5', '4': '5', '5': '7', '6': '7'}[ls[i]]

def promote_dig(ls, i):
	if i < 0:
		ls.insert(0, '2')
	elif ls[i] == '7':
		ls[i] = '2'
		promote_dig(ls, i - 1)
	else:
		ls[i] = {'2': '3', '3': '5', '5': '7'}[ls[i]]

def promote_next(ls):
	if ls[-1] == '3':
		ls[-1] = '7'
	elif ls[-1] == '7':
		ls[-1] = '3'
		promote_dig(ls, len(ls) - 2)
(N1, N2) = map(int, input().split())
nmegaprimes = 0
if N1 < 7:
	nmegaprimes = {1: 3, 2: 3, 3: 2, 4: 1, 5: 1, 6: 0}[N1]
	N1 = 7
sN1 = str(N1)
lsN1 = list(sN1)
for i in range(len(lsN1)):
	if lsN1[i] not in ('2', '3', '5', '7'):
		promoteN1(lsN1, i)
		lsN1[i + 1:] = '2' * len(lsN1[i + 1:])
		break
if lsN1[-1] == '2':
	lsN1[-1] = '3'
elif lsN1[-1] == '5':
	lsN1[-1] = '7'
n = ls2num(lsN1)
while n <= N2:
	if isprime(n):
		nmegaprimes += 1
	promote_next(lsN1)
	n = ls2num(lsN1)
print(nmegaprimes)


import sys

def try_composite(a, d, n, s):
	if pow(a, d, n) == 1:
		return False
	for i in range(s):
		if pow(a, 2 ** i * d, n) == n - 1:
			return False
	return True

def is_prime(n, precision_for_huge_n=16):
	if n in known_primes or n in (0, 1):
		return True
	if any((n % p == 0 for p in known_primes)):
		return False
	(d, s) = (n - 1, 0)
	while not d % 2:
		(d, s) = (d >> 1, s + 1)
	if n < 1373653:
		return not any((try_composite(a, d, n, s) for a in (2, 3)))
	if n < 25326001:
		return not any((try_composite(a, d, n, s) for a in (2, 3, 5)))
	if n < 118670087467:
		if n == 3215031751:
			return False
		return not any((try_composite(a, d, n, s) for a in (2, 3, 5, 7)))
	if n < 2152302898747:
		return not any((try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11)))
	if n < 3474749660383:
		return not any((try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13)))
	if n < 341550071728321:
		return not any((try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17)))
	if n < 3825123056546413051:
		return not any((try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17, 19, 23)))
	return not any((try_composite(a, d, n, s) for a in known_primes[:precision_for_huge_n]))

def set_values(i, a):
	for j in range(i, len(a)):
		a[j] = 7

def init_start(x, a):
	n = len(a)
	i = n - 1
	while x > 0:
		a[i] = x % 10
		x //= 10
		i -= 1
	i = 0
	while a[i] == 0:
		i += 1
	while i < n:
		if a[i] == 0 or a[i] == 1:
			while a[i - 1] == 2:
				i -= 1
			if a[i - 1] == 0:
				a[i] = 0
				i += 1
			else:
				if a[i - 1] == 3:
					a[i - 1] = 2
				if a[i - 1] == 5:
					a[i - 1] = 3
				if a[i - 1] == 7:
					a[i - 1] = 5
			set_values(i, a)
			break
		if a[i] == 4:
			a[i] = 3
			set_values(i + 1, a)
			break
		if a[i] == 6:
			a[i] = 5
			set_values(i + 1, a)
			break
		if a[i] == 8 or a[i] == 9:
			a[i] = 7
			set_values(i + 1, a)
			break
		i += 1
	return a

def solve(i, p, first_call):
	k = 0
	d = 0
	while d != 7:
		if first_call:
			d = start[i]
		elif d == 0:
			d = 2
		elif d == 2:
			d = 3
		elif d == 3:
			d = 5
		elif d == 5:
			d = 7
		n = p * 10 + d
		if i + 1 < len(start):
			(ret, stop) = solve(i + 1, n, first_call)
			k += ret
			if stop:
				return (k, True)
		else:
			if n > last:
				return (k, True)
			if n > first and is_prime(n):
				k += 1
		first_call = False
	return (k, False)
known_primes = [2, 3]
known_primes += [x for x in range(5, 1000, 2) if is_prime(x)]
str = input()
(first, last) = (int(x) for x in str.strip().split(' '))
digits = [2, 3, 5, 7]
start = init_start(first, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
print(solve(0, 0, True)[0])


import sys

def miller_rabin_pass(a, s, d, n):
	a_to_power = pow(a, d, n)
	if a_to_power == 1:
		return True
	for i in range(s - 1):
		if a_to_power == n - 1:
			return True
		a_to_power = a_to_power * a_to_power % n
	return a_to_power == n - 1

def miller_rabin(n):
	if n < 2:
		return False
	if n in {2, 3, 5, 7, 11, 13, 17, 19, 23}:
		return True
	d = n - 1
	s = 0
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in {2, 3, 5, 7, 11, 13, 17, 19, 23}:
		if not miller_rabin_pass(a, s, d, n):
			return False
	return True
(first, last) = input().strip().split(' ')
(first, last) = [int(first), int(last)]
s = set()
s.add('2')
s.add('3')
s.add('5')
s.add('7')
if last <= 22222:
	m = first % 10
	j = (3 - m) % 10
	k = (7 - m) % 10
	count = 0
	for i in range(first + k, last + 1, 10):
		if set(str(i)).issubset(s):
			if miller_rabin(i):
				count += 1
	for i in range(first + j, last + 1, 10):
		if set(str(i)).issubset(s):
			if miller_rabin(i):
				count += 1
	if first <= 5 and last >= 5:
		count += 1
	if first <= 2 and last >= 2:
		count += 1
else:
	m = first % 100000000
	b = [23, 27, 33, 37, 53, 57, 73, 77]
	c = []
	for i1 in {2, 3, 5, 7}:
		for i2 in {2, 3, 5, 7}:
			for i3 in {2, 3, 5, 7}:
				for i4 in {2, 3, 5, 7}:
					for i5 in {2, 3, 5, 7}:
						for i6 in {2, 3, 5, 7}:
							for j in b:
								c.append(int(str(i1) + str(i2) + str(i3) + str(i4) + str(i5) + str(i6) + str(j)))
	a = []
	for i in c:
		a.append((i - m) % 100000000)
	count = 0
	for i in range(max(1, first), min(22222221, last) + 1):
		if set(str(i)).issubset(s):
			if miller_rabin(i):
				count += 1
	for i in range(32768):
		for j in range(first + a[i], last + 1, 100000000):
			if set(str(j)).issubset(s):
				if miller_rabin(j):
					count += 1
print(count)


import sys
import sys
import math
from itertools import *
import sys

def tryComposite(a, d, n, s):
	if pow(a, d, n) == 1:
		return False
	for i in range(s):
		if pow(a, 2 ** i * d, n) == n - 1:
			return False
	return True
normDigits = [2, 2, 2, 3, 5, 5, 7, 7, 2, 2, 2]

def initNext(a):
	carry = 0
	twos = len(a)
	for i in range(len(a)):
		ao = a[i] + carry
		carry = ao > 7
		if carry:
			twos = i
		a[i] = normDigits[ao]
		if a[i] != ao:
			twos = i
	if carry:
		a.append(2)
	for i in range(twos):
		a[i] = 2
	return a
nextDigits = [2, 2, 3, 5, 5, 7, 7, 2, 2, 2]

def getNextNum(a):
	carry = True
	for i in range(len(a)):
		a[i] = nextDigits[a[i]]
		if a[i] != 2:
			carry = False
			break
	if carry:
		a.append(2)
	if len(a) > 1 and (a[0] == 2 or a[0] == 5):
		a[0] = nextDigits[a[0]]
	return a

def toInt(a):
	res = 0
	for n in a[::-1]:
		res = res * 10 + n
	return res

def isLess(a, b):
	if len(a) == len(b):
		for i in range(len(a) - 1, -1, -1):
			if a[i] == b[i]:
				continue
			return a[i] < b[i]
		return False
	return len(a) < len(b)

def isPrime(n):
	millerRabinTests = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
	if n in millerRabinTests or n in (0, 1):
		return True
	if any((n % p == 0 for p in millerRabinTests)):
		return False
	(d, s) = (n - 1, 0)
	while not d % 2:
		(d, s) = (d >> 1, s + 1)
	testlim = len(millerRabinTests)
	if n < 3825123056546413051:
		testlim = min(testlim, 9)
	elif n < 341550071728321:
		testlim = 7
	elif n < 3474749660383:
		testlim = 6
	elif n < 2152302898747:
		testlim = 5
	elif n < 3215031751:
		testlim = 4
	elif n < 25326001:
		testlim = 3
	elif n < 1373653:
		testlim = 2
	return not any((tryComposite(a, d, n, s) for a in millerRabinTests[:testlim]))
(sL, sR) = input().strip().split()
L = list(map(lambda c: ord(c) - ord('0'), sL[::-1]))
R = list(map(lambda c: ord(c) - ord('0'), sR[::-1]))
L = initNext(L)
cnt = 0
while isLess(L, R):
	il = toInt(L)
	if isPrime(il):
		cnt += 1
	L = getNextNum(L)
print(cnt)


from itertools import product

def isProbablePrime(n, ar=None):
	if n <= 1:
		return False
	if n == 2:
		return True
	if n % 2 == 0:
		return False
	if n < 9:
		return True
	if n % 3 == 0:
		return False
	if n % 5 == 0:
		return False
	if not ar:
		if n < 1373653:
			ar = (2, 3)
		elif n < 9080191:
			ar = (31, 73)
		elif n < 4759123141:
			ar = (2, 7, 61)
		elif n < 2152302898747:
			ar = (2, 3, 5, 7, 11)
		elif n < 3474749660383:
			ar = (2, 3, 5, 7, 11, 13)
		elif n < 341550071728321:
			ar = (2, 3, 5, 7, 11, 13, 17)
		else:
			ar = (2, 325, 9375, 28178, 450775, 9780504, 1795265022)
	for a in ar:
		if a == n:
			continue
		(t, u) = (0, n - 1)
		while u & 1 == 0:
			t += 1
			u >>= 1
		xi1 = pow(a, u, n)
		for i in range(0, t):
			xi2 = xi1 * xi1 % n
			if xi2 == 1 and xi1 != 1 and (xi1 != n - 1):
				return False
			xi1 = xi2
		if xi1 != 1:
			return False
	return True

def solve(first, last):
	_first = str(first)
	_last = str(last)
	n = len(_last)
	_first = '0' * (n - len(_first)) + _first
	allowed = (0, 2, 3, 5, 7)
	(i, digits) = (0, [])
	while i < n and _first[i] == _last[i]:
		if int(_first[i]) not in allowed:
			return 0
		digits.append((_first[i],))
		i += 1
	if i < n:
		digits.append(tuple((str(d) for d in allowed if int(_first[i]) <= d <= int(_last[i]))))
		i += 1
	digits += [tuple((str(d) for d in allowed))] * (n - i)
	j = 0
	while not digits[j]:
		j += 1
	digits = digits[j:]
	count = 0
	for _p in product(*digits):
		p = int(''.join(_p))
		if set(str(p)) <= {'2', '3', '5', '7'} and first <= p <= last and isProbablePrime(p):
			count += 1
	return count
(first, last) = map(int, input().split())
print(solve(first, last))


from math import floor, log10, ceil
import itertools

def miller_rabin(n):
	if n < 2:
		return False
	if n == 2:
		return True
	if n == 3:
		return True
	if n & 1 == 0:
		return False
	witness = [2, 3, 5, 7, 11, 13, 17, 19]
	r = 0
	d = n - 1
	while d & 1 == 0:
		d >>= 1
		r += 1
	for a in [w for w in witness if w <= n - 2]:
		x = pow(a, d, n)
		if x == 1 or x == n - 1:
			continue
		for i in range(r):
			x = pow(x, 2, n)
			if x == 1:
				return False
			if x == n - 1:
				break
		else:
			return False
	return True
(first, last) = [int(x) for x in input().split()]
P = [10 ** i for i in range(20)]

def gd(x, n):
	return x // P[n] % 10
nudge = [2, 1, 1, 2, 1, 2, 1, 5, 4, 3]
valid = {2, 3, 5, 7}
twos = [0, 2, 22, 222, 2222, 22222, 222222, 2222222, 22222222, 222222222, 2222222222, 22222222222, 222222222222, 2222222222222, 22222222222222, 222222222222222]

def getnext(n):
	nd = 0
	tmp = n
	while tmp > 0:
		tmp //= 10
		nd += 1
	i = nd - 1
	while i >= 0:
		d = gd(n, i)
		if d not in valid:
			if d < 7:
				n += P[i] * nudge[d]
				n = n // P[i] * P[i] + twos[i]
				break
			else:
				n = n // P[i + 1] * P[i + 1] + twos[i + 1]
				carry = True
				while carry:
					i += 1
					d = gd(n, i)
					carry = d >= 7
					n += P[i] * nudge[d]
				break
		i -= 1
	return n

def tick(n):
	carry = True
	i = 0
	d = gd(n, i)
	n += P[i] * nudge[d]
	if n > 9:
		while carry:
			i += 1
			d = gd(n, i)
			if d in valid:
				break
			n += P[i] * nudge[d]
			carry = d >= 7
	return n
smallprimes = {2, 3, 5, 7, 11, 13, 17}
n = getnext(first)
cnt = 0
while n <= last:
	if n in smallprimes or (n % 2 and n % 3 and n % 5 and n % 7 and n % 11 and n % 13 and miller_rabin(n)):
		cnt += 1
	n = tick(n)
print(cnt)


import sys
from time import time
from random import randrange

def rdigit_gen(n):
	if n == 0:
		yield 0
	else:
		while n:
			yield (n % 10)
			n //= 10

def combine(rdd):
	(n, c) = (0, 1)
	for d in rdd:
		n += d * c
		c *= 10
	return n

def increment(rdd):
	c = 1
	for i in range(len(rdd)):
		rdd[i] += c
		c = 0
		if rdd[i] <= 2:
			rdd[i] = 2
		elif rdd[i] <= 3:
			rdd[i] = 3
		elif rdd[i] <= 5:
			rdd[i] = 5
		elif rdd[i] <= 7:
			rdd[i] = 7
		else:
			rdd[i] = 2
			c = 1
	if c == 1:
		rdd.append(2)

def match(rdd):
	for d in rdd:
		if d not in (2, 3, 5, 7):
			return False
	return True

def adapt(n):
	rdd = list(rdigit_gen(n))
	c = 0
	for (i, d) in enumerate(rdd):
		d += c
		c = 0
		if d in (2, 3, 5, 7):
			rdd[i] = d
		elif d < 2:
			rdd[i] = 2
			rdd[:i] = [2] * i
		elif d < 3:
			rdd[i] = 3
			rdd[:i] = [2] * i
		elif d < 5:
			rdd[i] = 5
			rdd[:i] = [2] * i
		elif rdd[i] < 7:
			rdd[i] = 7
			rdd[:i] = [2] * i
		else:
			rdd[i] = 2
			rdd[:i] = [2] * i
			c = 1
	if c == 1:
		rdd = [2] * (len(rdd) + 1)
	return combine(rdd)

def number_gen(fr, to):
	n = adapt(fr)
	rdd = list(rdigit_gen(n))
	while n <= to:
		yield n
		increment(rdd)
		n = combine(rdd)

def is_composite(n, accuracy):
	if n < 4:
		return False
	s = 0
	d = n - 1
	while d % 2 == 0:
		s += 1
		d = d // 2
	for _ in range(accuracy):
		a = randrange(2, n - 1)
		x = pow(a, d, n)
		if x == 1 or x == n - 1:
			continue
		for _ in range(s - 1):
			x = x ** 2 % n
			if x == 1:
				return True
			if x == n - 1:
				break
		if x != n - 1:
			return True
	return False

def solve(first, last):
	cnt = 0
	for n in number_gen(first, last):
		if not is_composite(n, 10):
			cnt += 1
			print('%d' % n, file=sys.stderr)
	return cnt

def solve_bf(first, last):
	cnt = 0
	for n in range(first, last + 1):
		if match(rdigit_gen(n)) and (not is_composite(n, 10)):
			cnt += 1
	return cnt
(first, last) = map(int, input().split())
print(solve(first, last))


def getNextDigit(d):
	if d < 2:
		return 2
	if d < 3:
		return 3
	if d < 5:
		return 5
	if d < 7:
		return 7
	return None

def getNumbersBetween(first, last):
	first_ = tuple(map(int, str(first)))
	number = [2] * len(first_)
	i = 0
	while i < len(first_) and first_[i] in {2, 3, 5, 7}:
		number[i] = first_[i]
		i += 1
	if i < len(first_):
		number[i] = getNextDigit(first_[i] - 1)
		if number[i] == None:
			number[i] = 2
			i -= 1
			report = True
			while report == True and i >= 0:
				number[i] = getNextDigit(number[i])
				report = number[i] == None
				if report:
					number[i] = 2
				i -= 1
			if report:
				number = [2] + number
	while True:
		number_ = int(''.join(map(str, number)))
		if number_ > last:
			return
		yield number_
		(i, report) = (len(number) - 1, True)
		while report == True and i >= 0:
			number[i] = getNextDigit(number[i])
			report = number[i] == None
			if report:
				number[i] = 2
			i -= 1
		if report:
			number = [2] + number

def isProbablePrime(n, ar=None):
	if n <= 1:
		return False
	if n == 2:
		return True
	if n % 2 == 0:
		return False
	if n < 9:
		return True
	if n % 3 == 0:
		return False
	if n % 5 == 0:
		return False
	if not ar:
		if n < 1373653:
			ar = (2, 3)
		elif n < 9080191:
			ar = (31, 73)
		elif n < 4759123141:
			ar = (2, 7, 61)
		elif n < 2152302898747:
			ar = (2, 3, 5, 7, 11)
		elif n < 3474749660383:
			ar = (2, 3, 5, 7, 11, 13)
		else:
			ar = (2, 3, 5, 7, 11, 13, 17)
	for a in ar:
		if a == n:
			continue
		(t, u) = (0, n - 1)
		while u & 1 == 0:
			t += 1
			u >>= 1
		xi1 = pow(a, u, n)
		for i in range(0, t):
			xi2 = xi1 * xi1 % n
			if xi2 == 1 and xi1 != 1 and (xi1 != n - 1):
				return False
			xi1 = xi2
		if xi1 != 1:
			return False
	return True
(first, last) = map(int, input().split())
print(sum((1 for n in getNumbersBetween(first, last) if isProbablePrime(n))))


from random import randrange
import sys

def miller_rabin(n, k=10):
	if n == 2 or n == 3 or n == 5 or (n == 7):
		return True
	if n % 2 == 0 or n % 5 == 0:
		return False

	def check(a, s, d, n):
		x = pow(a, d, n)
		if x == 1:
			return True
		for i in range(s - 1):
			if x == n - 1:
				return True
			x = pow(x, 2, n)
		return x == n - 1
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for i in range(k):
		a = randrange(2, n - 1)
		if not check(a, s, d, n):
			return False
	return True

def is_prime(n):
	if n <= 1:
		return False
	elif n == 2:
		return True
	elif n % 2 == 0:
		return False
	else:
		i = 3
		while i * i <= n:
			if n % i == 0:
				return False
			i = i + 2
		return True

def to4(q):
	digits = [2, 3, 5, 7]
	q += 1
	e = 1
	n = 0
	while q != 0:
		(q, r) = divmod(q - 1, 4)
		n += e * digits[r]
		e *= 10
	return n

def from4(s):
	digits = [0, 0, 0, 1, 0, 2, 0, 3, 0, 0]
	n = -1
	for d in str(s):
		d = digits[int(d)]
		n = 4 * (n + 1) + d
	return n
(start, end) = map(int, input().split())
carry = False
start4 = -1
for d in str(start):
	if carry:
		d = 3
	else:
		d = int(d)
		if d >= 7:
			d = 3
		elif d >= 5:
			d = 2
		elif d >= 3:
			d = 1
		elif d == 2:
			d = 0
		else:
			d = 3
			carry = True
			start4 -= 1
	start4 = 4 * (start4 + 1) + d
if start4 == -1:
	start4 = 0
answer = 0
i = start4
while True:
	n = to4(i)
	i += 1
	if n > end:
		break
	if n < start:
		continue
	if miller_rabin(n):
		answer += 1
print(answer)


import sys

def rep(j):
	return (2 * pow(10, j) - 1) // 9

def valid(d):
	if d == 2 or d == 3:
		return 1
	if d == 5 or d == 7:
		return 1
	return 0

def primetest(n):
	if n == 1:
		return 0
	lim = 20
	if n < lim:
		lim = int(n)
	for i in range(2, lim):
		if pow(i, n - 1, n) != 1:
			return 0
	return 1

def succ(term):
	temp = term
	j = 0
	while temp % 10 == 7:
		temp = temp // 10
		j = j + 1
	d = temp % 10
	if d == 2:
		return (temp + 1) * pow(10, j) + rep(j)
	if d == 3:
		return (temp + 2) * pow(10, j) + rep(j)
	if d == 5:
		return (temp + 2) * pow(10, j) + rep(j)
	return rep(j + 1)

def legal(first):
	digits = []
	for i in range(20):
		digits.append(0)
	temp = first
	len = 1
	while temp > 9:
		temp = temp // 10
		len = len + 1
	temp = first
	for i in range(1, len + 1):
		d = temp % 10
		temp = temp // 10
		digits[len - i] = d
	answer = 0
	for j in range(len):
		d = digits[j]
		if valid(d) == 1:
			answer = 10 * answer + d
		elif d < 7:
			while valid(d) == 0:
				d = d + 1
			answer = 10 * answer + d
			return answer * pow(10, len - 1 - j) + rep(len - j - 1)
		else:
			answer = succ(answer)
			return answer * pow(10, len - j) + rep(len - j)
	return answer
(first, last) = input().strip().split(' ')
(first, last) = [int(first), int(last)]
term = legal(first)
count = 0
while term <= last:
	if primetest(term) == 1:
		count = count + 1
	term = succ(term)
print(count)


import sys

def rep(j):
	return (2 * pow(10, j) - 1) // 9

def valid(d):
	if d == 2 or d == 3:
		return 1
	if d == 5 or d == 7:
		return 1
	return 0

def primetest(n):
	if n == 1:
		return 0
	lim = 20
	if n < lim:
		lim = int(n)
	for i in range(2, lim):
		if pow(i, n - 1, n) != 1:
			return 0
	return 1

def succ(term):
	temp = term
	j = 0
	while temp % 10 == 7:
		temp = temp // 10
		j = j + 1
	d = temp % 10
	if d == 2:
		return (temp + 1) * pow(10, j) + rep(j)
	if d == 3:
		return (temp + 2) * pow(10, j) + rep(j)
	if d == 5:
		return (temp + 2) * pow(10, j) + rep(j)
	return rep(j + 1)

def legal(first):
	digits = []
	for i in range(20):
		digits.append(0)
	temp = first
	len = 1
	while temp > 9:
		temp = temp // 10
		len = len + 1
	temp = first
	for i in range(1, len + 1):
		d = temp % 10
		temp = temp // 10
		digits[len - i] = d
	answer = 0
	for j in range(len):
		d = digits[j]
		if valid(d) == 1:
			answer = 10 * answer + d
		elif d < 7:
			while valid(d) == 0:
				d = d + 1
			answer = 10 * answer + d
			return answer * pow(10, len - 1 - j) + rep(len - j - 1)
		else:
			answer = succ(answer)
			return answer * pow(10, len - j) + rep(len - j)
	return answer
(first, last) = input().strip().split(' ')
(first, last) = [int(first), int(last)]
term = legal(first)
count = 0
while term <= last:
	if primetest(term) == 1:
		count = count + 1
	term = succ(term)
print(count)


import math
import os
import random
import re
import sys

def check_composite(n, s, d, a):
	x = pow(a, d, n)
	if x == 1 or x == n - 1:
		return False
	for y in range(1, s):
		x = x * x % n
		if x == 1:
			return True
		if x == n - 1:
			return False
	return True
small_primes = set([3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37])
small_is_prime = [s in small_primes for s in range(38)]
small_is_prime[2] = True
witnesses_bounds = [(341531, [9345883071009581737]), (716169301, [15, 13393019396194701]), (154639673381, [15, 176006322, 4221622697]), (47636622961201, [2, 2570940, 211991001, 3749873356]), (3770579582154547, [2, 2570940, 880937, 610386380, 4130785767])]
i64_witnesses = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]

def is_prime(n):
	if n < 38:
		return small_is_prime[n]
	for s in small_primes:
		if n % s == 0:
			return False
	d = n - 1
	s = 0
	while not d & 1:
		d >>= 1
		s += 1
	best_witnesses = i64_witnesses
	for (bound, bound_ws) in witnesses_bounds:
		if n < bound:
			best_witnesses = bound_ws
			break
	for a in best_witnesses:
		a %= n
		if a and check_composite(n, s, d, a):
			return False
	return True
p = {2, 3, 5, 7}

def nextt(x):
	n = x
	p = 1
	s = 0
	while n % 10 == 7:
		x = x - p * 5
		p = p * 10
		n = n // 10
	if n % 10 == 0 or n % 10 == 3 or n % 10 == 5:
		return x + p * 2
	if n % 10 == 2:
		return x + p
firstLast = input().split()
first = int(firstLast[0])
last = int(firstLast[1])
i = 0
try:
	s = list(str(first))
	while int(s[i]) in p:
		i = i + 1
	if int(s[i]) < 2:
		s[i] = str(2)
		i = i + 1
		while i < len(s):
			s[i] = '2'
			i = i + 1
	elif int(s[i]) < 5:
		s[i] = str(5)
		i = i + 1
		while i < len(s):
			s[i] = '2'
			i = i + 1
	elif int(s[i]) < 7:
		s[i] = str(7)
		i = i + 1
		while i < len(s):
			s[i] = '2'
			i = i + 1
	else:
		while i < len(s):
			s[i] = '7'
			i = i + 1
	first = int(''.join(s))
except:
	pass
nb = 0
while first <= last:
	if is_prime(first):
		nb = nb + 1
	first = nextt(first)
print(nb)


from random import randrange
import sys

def miller_rabin(n, k=10):
	if n == 2 or n == 3 or n == 5 or (n == 7):
		return True
	if n % 2 == 0 or n % 5 == 0:
		return False

	def check(a, s, d, n):
		x = pow(a, d, n)
		if x == 1:
			return True
		for i in range(s - 1):
			if x == n - 1:
				return True
			x = pow(x, 2, n)
		return x == n - 1
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for i in range(k):
		a = randrange(2, n - 1)
		if not check(a, s, d, n):
			return False
	return True

def to4(q):
	digits = [2, 3, 5, 7]
	q += 1
	e = 1
	n = 0
	while q != 0:
		(q, r) = divmod(q - 1, 4)
		n += e * digits[r]
		e *= 10
	return n

def from4(s):
	digits = [0, 0, 0, 1, 0, 2, 0, 3, 0, 0]
	n = -1
	for d in str(s):
		d = digits[int(d)]
		n = 4 * (n + 1) + d
	return n
(start, end) = map(int, input().split())
carry = False
start4 = -1
for d in str(start):
	if carry:
		d = 3
	else:
		d = int(d)
		if d >= 7:
			d = 3
		elif d >= 5:
			d = 2
		elif d >= 3:
			d = 1
		elif d == 2:
			d = 0
		else:
			d = 3
			carry = True
			start4 -= 1
	start4 = 4 * (start4 + 1) + d
if start4 == -1:
	start4 = 0
answer = 0
i = start4
while True:
	n = to4(i)
	i += 1
	if n > end:
		break
	if n < start:
		continue
	if miller_rabin(n):
		answer += 1
print(answer)


import math
import os
import re
import sys
from random import randrange

def miller_rabin(n, k=10):
	if n == 2 or n == 3 or n == 5 or (n == 7):
		return True
	if n % 2 == 0 or n % 5 == 0:
		return False

	def check(a, s, d, n):
		x = pow(a, d, n)
		if x == 1:
			return True
		for i in range(s - 1):
			if x == n - 1:
				return True
			x = pow(x, 2, n)
		return x == n - 1
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for i in range(k):
		a = randrange(2, n - 1)
		if not check(a, s, d, n):
			return False
	return True

def to4(q):
	digits = [2, 3, 5, 7]
	q += 1
	e = 1
	n = 0
	while q != 0:
		(q, r) = divmod(q - 1, 4)
		n += e * digits[r]
		e *= 10
	return n

def from4(s):
	digits = [0, 0, 0, 1, 0, 2, 0, 3, 0, 0]
	n = -1
	for d in str(s):
		d = digits[int(d)]
		n = 4 * (n + 1) + d
	return n
(start, end) = map(int, input().split())
carry = False
start4 = -1
for d in str(start):
	if carry:
		d = 3
	else:
		d = int(d)
		if d >= 7:
			d = 3
		elif d >= 5:
			d = 2
		elif d >= 3:
			d = 1
		elif d == 2:
			d = 0
		else:
			d = 3
			carry = True
			start4 -= 1
	start4 = 4 * (start4 + 1) + d
if start4 == -1:
	start4 = 0
answer = 0
i = start4
while True:
	n = to4(i)
	i += 1
	if n > end:
		break
	if n < start:
		continue
	if miller_rabin(n):
		answer += 1
print(answer)


from random import randrange
import sys

def miller_rabin(n, k=10):
	if n == 2 or n == 3 or n == 5 or (n == 7):
		return True
	if n % 2 == 0 or n % 5 == 0:
		return False

	def check(a, s, d, n):
		x = pow(a, d, n)
		if x == 1:
			return True
		for i in range(s - 1):
			if x == n - 1:
				return True
			x = pow(x, 2, n)
		return x == n - 1
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for i in range(k):
		a = randrange(2, n - 1)
		if not check(a, s, d, n):
			return False
	return True

def to4(q):
	digits = [2, 3, 5, 7]
	q += 1
	e = 1
	n = 0
	while q != 0:
		(q, r) = divmod(q - 1, 4)
		n += e * digits[r]
		e *= 10
	return n

def from4(s):
	digits = [0, 0, 0, 1, 0, 2, 0, 3, 0, 0]
	n = -1
	for d in str(s):
		d = digits[int(d)]
		n = 4 * (n + 1) + d
	return n
(start, end) = map(int, input().split())
carry = False
start4 = -1
for d in str(start):
	if carry:
		d = 3
	else:
		d = int(d)
		if d >= 7:
			d = 3
		elif d >= 5:
			d = 2
		elif d >= 3:
			d = 1
		elif d == 2:
			d = 0
		else:
			d = 3
			carry = True
			start4 -= 1
	start4 = 4 * (start4 + 1) + d
if start4 == -1:
	start4 = 0
answer = 0
i = start4
while True:
	n = to4(i)
	i += 1
	if n > end:
		break
	if n < start:
		continue
	if miller_rabin(n):
		answer += 1
print(answer)


from random import randrange
import sys

def miller_rabin(n, k=10):
	if n == 2 or n == 3 or n == 5 or (n == 7):
		return True
	if n % 2 == 0 or n % 5 == 0:
		return False

	def check(a, s, d, n):
		x = pow(a, d, n)
		if x == 1:
			return True
		for i in range(s - 1):
			if x == n - 1:
				return True
			x = pow(x, 2, n)
		return x == n - 1
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for i in range(k):
		a = randrange(2, n - 1)
		if not check(a, s, d, n):
			return False
	return True

def to4(q):
	digits = [2, 3, 5, 7]
	q += 1
	e = 1
	n = 0
	while q != 0:
		(q, r) = divmod(q - 1, 4)
		n += e * digits[r]
		e *= 10
	return n

def from4(s):
	digits = [0, 0, 0, 1, 0, 2, 0, 3, 0, 0]
	n = -1
	for d in str(s):
		d = digits[int(d)]
		n = 4 * (n + 1) + d
	return n
(start, end) = map(int, input().split())
carry = False
start4 = -1
for d in str(start):
	if carry:
		d = 3
	else:
		d = int(d)
		if d >= 7:
			d = 3
		elif d >= 5:
			d = 2
		elif d >= 3:
			d = 1
		elif d == 2:
			d = 0
		else:
			d = 3
			carry = True
			start4 -= 1
	start4 = 4 * (start4 + 1) + d
if start4 == -1:
	start4 = 0
answer = 0
i = start4
while True:
	n = to4(i)
	i += 1
	if n > end:
		break
	if n < start:
		continue
	if miller_rabin(n):
		answer += 1
print(answer)


import math
import os
from random import randrange
import re
import sys

def miller_rabin(n, k=10):
	if n == 2 or n == 3 or n == 5 or (n == 7):
		return True
	if n % 2 == 0 or n % 5 == 0:
		return False

	def check(a, s, d, n):
		x = pow(a, d, n)
		if x == 1:
			return True
		for i in range(s - 1):
			if x == n - 1:
				return True
			x = pow(x, 2, n)
		return x == n - 1
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for i in range(k):
		a = randrange(2, n - 1)
		if not check(a, s, d, n):
			return False
	return True

def to4(q):
	digits = [2, 3, 5, 7]
	q += 1
	e = 1
	n = 0
	while q != 0:
		(q, r) = divmod(q - 1, 4)
		n += e * digits[r]
		e *= 10
	return n

def from4(s):
	digits = [0, 0, 0, 1, 0, 2, 0, 3, 0, 0]
	n = -1
	for d in str(s):
		d = digits[int(d)]
		n = 4 * (n + 1) + d
	return n
firstLast = input().split()
first = int(firstLast[0])
last = int(firstLast[1])
carry = False
start4 = -1
for d in str(first):
	if carry:
		d = 3
	else:
		d = int(d)
		if d >= 7:
			d = 3
		elif d >= 5:
			d = 2
		elif d >= 3:
			d = 1
		elif d == 2:
			d = 0
		else:
			d = 3
			carry = True
			start4 -= 1
	start4 = 4 * (start4 + 1) + d
if start4 == -1:
	start4 = 0
answer = 0
i = start4
while True:
	n = to4(i)
	i += 1
	if n > last:
		break
	if n < first:
		continue
	if miller_rabin(n):
		answer += 1
print(answer)


import os, sys, math

def miller_rabin(n):
	if n < 3825123056546413051:
		bases = [2, 3, 5, 7, 11, 13, 17, 19, 23]
	else:
		raise ValueError(n)
	prime_bases = [2, 3, 5, 7, 11, 13, 17, 19, 23]
	if n < 2:
		return False
	if n == 2 or n in prime_bases:
		return True
	if n % 2 == 0:
		return False
	(r, s) = (0, n - 1)
	while s % 2 == 0:
		r += 1
		s //= 2
	for a in bases:
		x = pow(a, s, n)
		if x == 1 or x == n - 1:
			continue
		for _ in range(r - 1):
			x = pow(x, 2, n)
			if x == n - 1:
				break
		else:
			return False
	return True
validDigits = [2, 3, 5, 7]
nextValidDigits = [2, 2, 3, 5, 5, 7, 7, 2, 2, 2]
previousValidDigits = [7, 7, 7, 2, 3, 3, 5, 5, 7, 7]
incrementValidMap = [-1, -1, 3, 5, -1, 7, -1, 2, -1, -1]

def nextValid(a):
	i = len(a) - 1
	while i >= 0 and a[i] in validDigits:
		i -= 1
	if i < 0:
		return a
	i1 = i
	while True:
		x = a[i]
		a[i] = nextValidDigits[x]
		if a[i] > x:
			break
		if i + 1 >= len(a):
			a.append(2)
			break
		i += 1
	for i in range(0, i1):
		a[i] = 2
	return a

def previousValid(a):
	i = len(a) - 1
	while i >= 0 and a[i] in validDigits:
		i -= 1
	if i < 0:
		return a
	i1 = i
	while True:
		x = a[i]
		a[i] = previousValidDigits[x]
		if a[i] < x:
			break
		if i + 1 >= len(a):
			a.pop()
			break
		i += 1
	for i in range(0, i1):
		a[i] = 7
	return a

def incrementValid(a):
	i = 0
	while i <= len(a):
		if i == len(a):
			a.append(2)
			break
		elif a[i] == 7:
			a[i] = 2
		else:
			a[i] = incrementValidMap[a[i]]
			break
		i += 1

def intFromDigits(a):
	s = 0
	dsum = 0
	p = 1
	for x in a:
		dsum += x
		s += p * x
		p *= 10
	return (s, dsum)

def passed_composite_tests(x, dsum):
	if dsum % 3 == 0 and x != 3:
		return True
	for p in [2, 3, 5, 7, 11, 13]:
		if x % p == 0 and x != p:
			return True
	return False

def countMegaPrimes(first, last):
	first = nextValid([int(c) for c in reversed(str(first))])
	last = previousValid([int(c) for c in reversed(str(last))])
	(first1, _) = intFromDigits(first)
	(last1, _) = intFromDigits(last)
	if first1 > last1:
		return 0
	x = first
	c = 0
	while True:
		(y, dsum) = intFromDigits(x)
		if not passed_composite_tests(y, dsum) and miller_rabin(y):
			c += 1
		if x == last:
			break
		incrementValid(x)
	return c

def main():
	firstLast = input().split()
	first = int(firstLast[0])
	last = int(firstLast[1])
	print(countMegaPrimes(first, last))
main()


import math
import os
import random
import re
import sys
primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973, 10007, 10009, 10037, 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099, 10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163, 10169, 10177, 10181, 10193, 10211, 10223, 10243, 10247, 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303, 10313, 10321, 10331, 10333, 10337, 10343, 10357, 10369, 10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459, 10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531, 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639, 10651, 10657, 10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733, 10739, 10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859, 10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949, 10957, 10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059, 11069, 11071, 11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149, 11159, 11161, 11171, 11173, 11177, 11197, 11213, 11239, 11243, 11251, 11257, 11261, 11273, 11279, 11287, 11299, 11311, 11317, 11321, 11329, 11351, 11353, 11369, 11383, 11393, 11399, 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483, 11489, 11491, 11497, 11503, 11519, 11527, 11549, 11551, 11579, 11587, 11593, 11597, 11617, 11621, 11633, 11657, 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731, 11743, 11777, 11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831, 11833, 11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933, 11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011, 12037, 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109, 12113, 12119, 12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211, 12227, 12239, 12241, 12251, 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323, 12329, 12343, 12347, 12373, 12377, 12379, 12391, 12401, 12409, 12413, 12421, 12433, 12437, 12451, 12457, 12473, 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527, 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589, 12601, 12611, 12613, 12619, 12637, 12641, 12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713, 12721, 12739, 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823, 12829, 12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923, 12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007, 13009, 13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109, 13121, 13127, 13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187, 13217, 13219, 13229, 13241, 13249, 13259, 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337, 13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421, 13441, 13451, 13457, 13463, 13469, 13477, 13487, 13499, 13513, 13523, 13537, 13553, 13567, 13577, 13591, 13597, 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681, 13687, 13691, 13693, 13697, 13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759, 13763, 13781, 13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877, 13879, 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967, 13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081, 14083, 14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221, 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323, 14327, 14341, 14347, 14369, 14387, 14389, 14401, 14407, 14411, 14419, 14423, 14431, 14437, 14447, 14449, 14461, 14479, 14489, 14503, 14519, 14533, 14537, 14543, 14549, 14551, 14557, 14561, 14563, 14591, 14593, 14621, 14627, 14629, 14633, 14639, 14653, 14657, 14669, 14683, 14699, 14713, 14717, 14723, 14731, 14737, 14741, 14747, 14753, 14759, 14767, 14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831, 14843, 14851, 14867, 14869, 14879, 14887, 14891, 14897, 14923, 14929, 14939, 14947, 14951, 14957, 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073, 15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139, 15149, 15161, 15173, 15187, 15193, 15199, 15217, 15227, 15233, 15241, 15259, 15263, 15269, 15271, 15277, 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331, 15349, 15359, 15361, 15373, 15377, 15383, 15391, 15401, 15413, 15427, 15439, 15443, 15451, 15461, 15467, 15473, 15493, 15497, 15511, 15527, 15541, 15551, 15559, 15569, 15581, 15583, 15601, 15607, 15619, 15629, 15641, 15643, 15647, 15649, 15661, 15667, 15671, 15679, 15683, 15727, 15731, 15733, 15737, 15739, 15749, 15761, 15767, 15773, 15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859, 15877, 15881, 15887, 15889, 15901, 15907, 15913, 15919, 15923, 15937, 15959, 15971, 15973, 15991, 16001, 16007, 16033, 16057, 16061, 16063, 16067, 16069, 16073, 16087, 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183, 16187, 16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267, 16273, 16301, 16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381, 16411, 16417, 16421, 16427, 16433, 16447, 16451, 16453, 16477, 16481, 16487, 16493, 16519, 16529, 16547, 16553, 16561, 16567, 16573, 16603, 16607, 16619, 16631, 16633, 16649, 16651, 16657, 16661, 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747, 16759, 16763, 16787, 16811, 16823, 16829, 16831, 16843, 16871, 16879, 16883, 16889, 16901, 16903, 16921, 16927, 16931, 16937, 16943, 16963, 16979, 16981, 16987, 16993, 17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053, 17077, 17093, 17099, 17107, 17117, 17123, 17137, 17159, 17167, 17183, 17189, 17191, 17203, 17207, 17209, 17231, 17239, 17257, 17291, 17293, 17299, 17317, 17321, 17327, 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389, 17393, 17401, 17417, 17419, 17431, 17443, 17449, 17467, 17471, 17477, 17483, 17489, 17491, 17497, 17509, 17519, 17539, 17551, 17569, 17573, 17579, 17581, 17597, 17599, 17609, 17623, 17627, 17657, 17659, 17669, 17681, 17683, 17707, 17713, 17729, 17737, 17747, 17749, 17761, 17783, 17789, 17791, 17807, 17827, 17837, 17839, 17851, 17863, 17881, 17891, 17903, 17909, 17911, 17921, 17923, 17929, 17939, 17957, 17959, 17971, 17977, 17981, 17987, 17989, 18013, 18041, 18043, 18047, 18049, 18059, 18061, 18077, 18089, 18097, 18119, 18121, 18127, 18131, 18133, 18143, 18149, 18169, 18181, 18191, 18199, 18211, 18217, 18223, 18229, 18233, 18251, 18253, 18257, 18269, 18287, 18289, 18301, 18307, 18311, 18313, 18329, 18341, 18353, 18367, 18371, 18379, 18397, 18401, 18413, 18427, 18433, 18439, 18443, 18451, 18457, 18461, 18481, 18493, 18503, 18517, 18521, 18523, 18539, 18541, 18553, 18583, 18587, 18593, 18617, 18637, 18661, 18671, 18679, 18691, 18701, 18713, 18719, 18731, 18743, 18749, 18757, 18773, 18787, 18793, 18797, 18803, 18839, 18859, 18869, 18899, 18911, 18913, 18917, 18919, 18947, 18959, 18973, 18979, 19001, 19009, 19013, 19031, 19037, 19051, 19069, 19073, 19079, 19081, 19087, 19121, 19139, 19141, 19157, 19163, 19181, 19183, 19207, 19211, 19213, 19219, 19231, 19237, 19249, 19259, 19267, 19273, 19289, 19301, 19309, 19319, 19333, 19373, 19379, 19381, 19387, 19391, 19403, 19417, 19421, 19423, 19427, 19429, 19433, 19441, 19447, 19457, 19463, 19469, 19471, 19477, 19483, 19489, 19501, 19507, 19531, 19541, 19543, 19553, 19559, 19571, 19577, 19583, 19597, 19603, 19609, 19661, 19681, 19687, 19697, 19699, 19709, 19717, 19727, 19739, 19751, 19753, 19759, 19763, 19777, 19793, 19801, 19813, 19819, 19841, 19843, 19853, 19861, 19867, 19889, 19891, 19913, 19919, 19927, 19937, 19949, 19961, 19963, 19973, 19979, 19991, 19993, 19997, 20011, 20021, 20023, 20029, 20047, 20051, 20063, 20071, 20089, 20101, 20107, 20113, 20117, 20123, 20129, 20143, 20147, 20149, 20161, 20173, 20177, 20183, 20201, 20219, 20231, 20233, 20249, 20261, 20269, 20287, 20297, 20323, 20327, 20333, 20341, 20347, 20353, 20357, 20359, 20369, 20389, 20393, 20399, 20407, 20411, 20431, 20441, 20443, 20477, 20479, 20483, 20507, 20509, 20521, 20533, 20543, 20549, 20551, 20563, 20593, 20599, 20611, 20627, 20639, 20641, 20663, 20681, 20693, 20707, 20717, 20719, 20731, 20743, 20747, 20749, 20753, 20759, 20771, 20773, 20789, 20807, 20809, 20849, 20857, 20873, 20879, 20887, 20897, 20899, 20903, 20921, 20929, 20939, 20947, 20959, 20963, 20981, 20983, 21001, 21011, 21013, 21017, 21019, 21023, 21031, 21059, 21061, 21067, 21089, 21101, 21107, 21121, 21139, 21143, 21149, 21157, 21163, 21169, 21179, 21187, 21191, 21193, 21211, 21221, 21227, 21247, 21269, 21277, 21283, 21313, 21317, 21319, 21323, 21341, 21347, 21377, 21379, 21383, 21391, 21397, 21401, 21407, 21419, 21433, 21467, 21481, 21487, 21491, 21493, 21499, 21503, 21517, 21521, 21523, 21529, 21557, 21559, 21563, 21569, 21577, 21587, 21589, 21599, 21601, 21611, 21613, 21617, 21647, 21649, 21661, 21673, 21683, 21701, 21713, 21727, 21737, 21739, 21751, 21757, 21767, 21773, 21787, 21799, 21803, 21817, 21821, 21839, 21841, 21851, 21859, 21863, 21871, 21881, 21893, 21911, 21929, 21937, 21943, 21961, 21977, 21991, 21997, 22003, 22013, 22027, 22031, 22037, 22039, 22051, 22063, 22067, 22073, 22079, 22091, 22093, 22109, 22111, 22123, 22129, 22133, 22147, 22153, 22157, 22159, 22171, 22189, 22193, 22229, 22247, 22259, 22271, 22273, 22277, 22279, 22283, 22291, 22303, 22307, 22343, 22349, 22367, 22369, 22381, 22391, 22397, 22409, 22433, 22441, 22447, 22453, 22469, 22481, 22483, 22501, 22511, 22531, 22541, 22543, 22549, 22567, 22571, 22573, 22613, 22619, 22621, 22637, 22639, 22643, 22651, 22669, 22679, 22691, 22697, 22699, 22709, 22717, 22721, 22727, 22739, 22741, 22751, 22769, 22777, 22783, 22787, 22807, 22811, 22817, 22853, 22859, 22861, 22871, 22877, 22901, 22907, 22921, 22937, 22943, 22961, 22963, 22973, 22993, 23003, 23011, 23017, 23021, 23027, 23029, 23039, 23041, 23053, 23057, 23059, 23063, 23071, 23081, 23087, 23099, 23117, 23131, 23143, 23159, 23167, 23173, 23189, 23197, 23201, 23203, 23209, 23227, 23251, 23269, 23279, 23291, 23293, 23297, 23311, 23321, 23327, 23333, 23339, 23357, 23369, 23371, 23399, 23417, 23431, 23447, 23459, 23473, 23497, 23509, 23531, 23537, 23539, 23549, 23557, 23561, 23563, 23567, 23581, 23593, 23599, 23603, 23609, 23623, 23627, 23629, 23633, 23663, 23669, 23671, 23677, 23687, 23689, 23719, 23741, 23743, 23747, 23753, 23761, 23767, 23773, 23789, 23801, 23813, 23819, 23827, 23831, 23833, 23857, 23869, 23873, 23879, 23887, 23893, 23899, 23909, 23911, 23917, 23929, 23957, 23971, 23977, 23981, 23993, 24001, 24007, 24019, 24023, 24029, 24043, 24049, 24061, 24071, 24077, 24083, 24091, 24097, 24103, 24107, 24109, 24113, 24121, 24133, 24137, 24151, 24169, 24179, 24181, 24197, 24203, 24223, 24229, 24239, 24247, 24251, 24281, 24317, 24329, 24337, 24359, 24371, 24373, 24379, 24391, 24407, 24413, 24419, 24421, 24439, 24443, 24469, 24473, 24481, 24499, 24509, 24517, 24527, 24533, 24547, 24551, 24571, 24593, 24611, 24623, 24631, 24659, 24671, 24677, 24683, 24691, 24697, 24709, 24733, 24749, 24763, 24767, 24781, 24793, 24799, 24809, 24821, 24841, 24847, 24851, 24859, 24877, 24889, 24907, 24917, 24919, 24923, 24943, 24953, 24967, 24971, 24977, 24979, 24989, 25013, 25031, 25033, 25037, 25057, 25073, 25087, 25097, 25111, 25117, 25121, 25127, 25147, 25153, 25163, 25169, 25171, 25183, 25189, 25219, 25229, 25237, 25243, 25247, 25253, 25261, 25301, 25303, 25307, 25309, 25321, 25339, 25343, 25349, 25357, 25367, 25373, 25391, 25409, 25411, 25423, 25439, 25447, 25453, 25457, 25463, 25469, 25471, 25523, 25537, 25541, 25561, 25577, 25579, 25583, 25589, 25601, 25603, 25609, 25621, 25633, 25639, 25643, 25657, 25667, 25673, 25679, 25693, 25703, 25717, 25733, 25741, 25747, 25759, 25763, 25771, 25793, 25799, 25801, 25819, 25841, 25847, 25849, 25867, 25873, 25889, 25903, 25913, 25919, 25931, 25933, 25939, 25943, 25951, 25969, 25981, 25997, 25999, 26003, 26017, 26021, 26029, 26041, 26053, 26083, 26099, 26107, 26111, 26113, 26119, 26141, 26153, 26161, 26171, 26177, 26183, 26189, 26203, 26209, 26227, 26237, 26249, 26251, 26261, 26263, 26267, 26293, 26297, 26309, 26317, 26321, 26339, 26347, 26357, 26371, 26387, 26393, 26399, 26407, 26417, 26423, 26431, 26437, 26449, 26459, 26479, 26489, 26497, 26501, 26513, 26539, 26557, 26561, 26573, 26591, 26597, 26627, 26633, 26641, 26647, 26669, 26681, 26683, 26687, 26693, 26699, 26701, 26711, 26713, 26717, 26723, 26729, 26731, 26737, 26759, 26777, 26783, 26801, 26813, 26821, 26833, 26839, 26849, 26861, 26863, 26879, 26881, 26891, 26893, 26903, 26921, 26927, 26947, 26951, 26953, 26959, 26981, 26987, 26993, 27011, 27017, 27031, 27043, 27059, 27061, 27067, 27073, 27077, 27091, 27103, 27107, 27109, 27127, 27143, 27179, 27191, 27197, 27211, 27239, 27241, 27253, 27259, 27271, 27277, 27281, 27283, 27299, 27329, 27337, 27361, 27367, 27397, 27407, 27409, 27427, 27431, 27437, 27449, 27457, 27479, 27481, 27487, 27509, 27527, 27529, 27539, 27541, 27551, 27581, 27583, 27611, 27617, 27631, 27647, 27653, 27673, 27689, 27691, 27697, 27701, 27733, 27737, 27739, 27743, 27749, 27751, 27763, 27767, 27773, 27779, 27791, 27793, 27799, 27803, 27809, 27817, 27823, 27827, 27847, 27851, 27883, 27893, 27901, 27917, 27919, 27941, 27943, 27947, 27953, 27961, 27967, 27983, 27997, 28001, 28019, 28027, 28031, 28051, 28057, 28069, 28081, 28087, 28097, 28099, 28109, 28111, 28123, 28151, 28163, 28181, 28183, 28201, 28211, 28219, 28229, 28277, 28279, 28283, 28289, 28297, 28307, 28309, 28319, 28349, 28351, 28387, 28393, 28403, 28409, 28411, 28429, 28433, 28439, 28447, 28463, 28477, 28493, 28499, 28513, 28517, 28537, 28541, 28547, 28549, 28559, 28571, 28573, 28579, 28591, 28597, 28603, 28607, 28619, 28621, 28627, 28631, 28643, 28649, 28657, 28661, 28663, 28669, 28687, 28697, 28703, 28711, 28723, 28729, 28751, 28753, 28759, 28771, 28789, 28793, 28807, 28813, 28817, 28837, 28843, 28859, 28867, 28871, 28879, 28901, 28909, 28921, 28927, 28933, 28949, 28961, 28979, 29009, 29017, 29021, 29023, 29027, 29033, 29059, 29063, 29077, 29101, 29123, 29129, 29131, 29137, 29147, 29153, 29167, 29173, 29179, 29191, 29201, 29207, 29209, 29221, 29231, 29243, 29251, 29269, 29287, 29297, 29303, 29311, 29327, 29333, 29339, 29347, 29363, 29383, 29387, 29389, 29399, 29401, 29411, 29423, 29429, 29437, 29443, 29453, 29473, 29483, 29501, 29527, 29531, 29537, 29567, 29569, 29573, 29581, 29587, 29599, 29611, 29629, 29633, 29641, 29663, 29669, 29671, 29683, 29717, 29723, 29741, 29753, 29759, 29761, 29789, 29803, 29819, 29833, 29837, 29851, 29863, 29867, 29873, 29879, 29881, 29917, 29921, 29927, 29947, 29959, 29983, 29989, 30011, 30013, 30029, 30047, 30059, 30071, 30089, 30091, 30097, 30103, 30109, 30113, 30119, 30133, 30137, 30139, 30161, 30169, 30181, 30187, 30197, 30203, 30211, 30223, 30241, 30253, 30259, 30269, 30271, 30293, 30307, 30313, 30319, 30323, 30341, 30347, 30367, 30389, 30391, 30403, 30427, 30431, 30449, 30467, 30469, 30491, 30493, 30497, 30509, 30517, 30529, 30539, 30553, 30557, 30559, 30577, 30593, 30631, 30637, 30643, 30649, 30661, 30671, 30677, 30689, 30697, 30703, 30707, 30713, 30727, 30757, 30763, 30773, 30781, 30803, 30809, 30817, 30829, 30839, 30841, 30851, 30853, 30859, 30869, 30871, 30881, 30893, 30911, 30931, 30937, 30941, 30949, 30971, 30977, 30983, 31013, 31019, 31033, 31039, 31051, 31063, 31069, 31079, 31081, 31091, 31121, 31123, 31139, 31147, 31151, 31153, 31159, 31177, 31181, 31183, 31189, 31193, 31219, 31223, 31231, 31237, 31247, 31249, 31253, 31259, 31267, 31271, 31277, 31307, 31319, 31321, 31327, 31333, 31337, 31357, 31379, 31387, 31391, 31393, 31397, 31469, 31477, 31481, 31489, 31511, 31513, 31517, 31531, 31541, 31543, 31547, 31567, 31573, 31583, 31601, 31607, 31627, 31643, 31649, 31657, 31663, 31667, 31687, 31699, 31721, 31723, 31727, 31729, 31741, 31751, 31769, 31771, 31793, 31799, 31817, 31847, 31849, 31859, 31873, 31883, 31891, 31907, 31957, 31963, 31973, 31981, 31991, 32003)

def isPrime(n):
	if n < 2:
		return False
	if n == 2:
		return True
	if not n & 1:
		return False
	if n <= 32000:
		return n in primes
	for p in primes[:10]:
		if n % p == 0:
			return False
	for a in range(10):
		if pow(random.randint(3, n - 2), n - 1, n) != 1:
			return False
	return True
prime_digits = (2, 3, 5, 7)
prime_digits_indices = {2: 0, 3: 1, 5: 2, 7: 3}

def normalize_first(digits):
	index = 0
	while index < len(digits) and digits[index] in prime_digits:
		index += 1
	if index == len(digits):
		return [prime_digits_indices[i] for i in digits]
	while index >= 0 and digits[index] >= 7:
		index -= 1
	if index < 0:
		return [prime_digits_indices[2] for _ in len(digits) + 1]
	digits[index] += 1
	while digits[index] not in prime_digits:
		digits[index] += 1
	for i in range(index + 1, len(digits)):
		digits[i] = 2
	return [prime_digits_indices[i] for i in digits]

def number(digit_indices):
	pow10 = 1
	result = 0
	for idx in digit_indices[::-1]:
		result += pow10 * prime_digits[idx]
		pow10 *= 10
	return result

def next(indices, number):
	index = len(indices) - 1
	diff = 0
	while index >= 0 and indices[index] == 3:
		indices[index] = 0
		diff = diff * 10 - 5
		index -= 1
	if index < 0:
		indices.insert(0, 0)
		index = 0
		start = 0
		end = 2
	else:
		start = prime_digits[indices[index]]
		indices[index] += 1
		end = prime_digits[indices[index]]
	return number + diff + (end - start) * 10 ** (len(indices) - index - 1)
(first_str, last_str) = input().split()
last = int(last_str)
first_digits = list(map(int, first_str))
indices = normalize_first(first_digits)
number = number(indices)
result = 0
while number <= last:
	if isPrime(number):
		result += 1
	number = next(indices, number)
print(result)


import sys

def miller_rabin2(p, a):
	d = p - 1
	s = 0
	while d & 1 == 0:
		d = d >> 1
		s += 1
	r = pow(a, d, p)
	if r == 1 or r == p - 1:
		return True
	for _ in range(s - 1):
		r = r * r % p
		if r == p - 1:
			return True
	return False

def miller_rabin(p):
	for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
		if a >= p:
			return True
		if not miller_rabin2(p, a):
			return False
	return True

def mega_range(first, last):
	nxt = {0: 2, 1: 1, 2: 0, 3: 0, 4: 1, 5: 0, 6: 1, 7: 0, 8: 4, 9: 3}
	powers10 = [10 ** i for i in range(20)]
	last_digit = {3, 7}
	x = first
	for mag in reversed(powers10):
		if mag > x:
			continue
		inc = nxt[x // mag % 10]
		if inc:
			x += mag * inc
			mag = mag // 10
			while mag:
				x = x - x % (mag * 10) + mag + mag
				mag = mag // 10
	while x <= last:
		if x % 10 in last_digit or x < 10:
			yield x
		x += 1
		for mag in powers10:
			if mag > x:
				break
			x += mag * nxt[x // mag % 10]
(first, last) = [int(x) for x in input().split()]
count = 0
for i in mega_range(first, last):
	if miller_rabin(i):
		count += 1
print(count)


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


import math
import os
import random
import re
import sys
from itertools import product

def is_prime0(n):
	if n <= 1:
		return False
	if n == 2:
		return True
	if n > 2 and n % 2 == 0:
		return False
	max_div = math.floor(math.sqrt(n))
	for i in range(3, 1 + max_div, 2):
		if n % i == 0:
			return False
	return True

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def is_prime(n, k=4):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
firstLast = input().split()
first = int(firstLast[0])
last = int(firstLast[1])
lp = ['2', '3', '5', '7']
s = ''
if len(firstLast[0]) == len(firstLast[1]):
	for i in range(len(firstLast[0])):
		if firstLast[0][i] == firstLast[1][i]:
			s = s + firstLast[0][i]
		else:
			break
count = 0
for i in range(1, 11):
	numbers = list(list(map(''.join, product('2357', repeat=i))))
	for i in range(len(numbers)):
		numbers[i] = s + numbers[i]
	if int(numbers[0]) > last:
		break
	for numb in numbers:
		if int(numb) > last:
			break
		if int(numb) >= first:
			if is_prime(int(numb)):
				count += 1
print(count)


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


import math
import os
import random
import re
import sys
import itertools
import random
(n, m) = map(int, input().strip().split(' '))

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = 0
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P += 1
print(P)


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


def getNextDigit(d):
	if d < 2:
		return 2
	if d < 3:
		return 3
	if d < 5:
		return 5
	if d < 7:
		return 7
	return None

def getNumbersBetween(first, last):
	first_ = tuple(map(int, str(first)))
	number = [2] * len(first_)
	i = 0
	while i < len(first_) and first_[i] in {2, 3, 5, 7}:
		number[i] = first_[i]
		i += 1
	if i < len(first_):
		number[i] = getNextDigit(first_[i] - 1)
		if number[i] == None:
			number[i] = 2
			i -= 1
			report = True
			while report == True and i >= 0:
				number[i] = getNextDigit(number[i])
				report = number[i] == None
				if report:
					number[i] = 2
				i -= 1
			if report:
				number = [2] + number
	while True:
		number_ = int(''.join(map(str, number)))
		if number_ > last:
			return
		yield number_
		(i, report) = (len(number) - 1, True)
		while report == True and i >= 0:
			number[i] = getNextDigit(number[i])
			report = number[i] == None
			if report:
				number[i] = 2
			i -= 1
		if report:
			number = [2] + number

def isProbablePrime(n, ar=None):
	if n <= 1:
		return False
	if n == 2:
		return True
	if n % 2 == 0:
		return False
	if n < 9:
		return True
	if n % 3 == 0:
		return False
	if n % 5 == 0:
		return False
	if not ar:
		if n < 1373653:
			ar = (2, 3)
		elif n < 9080191:
			ar = (31, 73)
		elif n < 4759123141:
			ar = (2, 7, 61)
		elif n < 2152302898747:
			ar = (2, 3, 5, 7, 11)
		elif n < 3474749660383:
			ar = (2, 3, 5, 7, 11, 13)
		else:
			ar = (2, 3, 5, 7, 11, 13, 17)
	for a in ar:
		if a == n:
			continue
		(t, u) = (0, n - 1)
		while u & 1 == 0:
			t += 1
			u >>= 1
		xi1 = pow(a, u, n)
		for i in range(0, t):
			xi2 = xi1 * xi1 % n
			if xi2 == 1 and xi1 != 1 and (xi1 != n - 1):
				return False
			xi1 = xi2
		if xi1 != 1:
			return False
	return True
(first, last) = map(int, input().split())
print(sum((1 for n in getNumbersBetween(first, last) if isProbablePrime(n))))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


from random import randrange
import sys

def miller_rabin(n, k=10):
	if n == 2 or n == 3 or n == 5 or (n == 7):
		return True
	if n % 2 == 0 or n % 5 == 0:
		return False

	def check(a, s, d, n):
		x = pow(a, d, n)
		if x == 1:
			return True
		for i in range(s - 1):
			if x == n - 1:
				return True
			x = pow(x, 2, n)
		return x == n - 1
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for i in range(k):
		a = randrange(2, n - 1)
		if not check(a, s, d, n):
			return False
	return True

def to4(q):
	digits = [2, 3, 5, 7]
	q += 1
	e = 1
	n = 0
	while q != 0:
		(q, r) = divmod(q - 1, 4)
		n += e * digits[r]
		e *= 10
	return n

def from4(s):
	digits = [0, 0, 0, 1, 0, 2, 0, 3, 0, 0]
	n = -1
	for d in str(s):
		d = digits[int(d)]
		n = 4 * (n + 1) + d
	return n
(start, end) = map(int, input().split())
carry = False
start4 = -1
for d in str(start):
	if carry:
		d = 3
	else:
		d = int(d)
		if d >= 7:
			d = 3
		elif d >= 5:
			d = 2
		elif d >= 3:
			d = 1
		elif d == 2:
			d = 0
		else:
			d = 3
			carry = True
			start4 -= 1
	start4 = 4 * (start4 + 1) + d
if start4 == -1:
	start4 = 0
answer = 0
i = start4
while True:
	n = to4(i)
	i += 1
	if n > end:
		break
	if n < start:
		continue
	if miller_rabin(n):
		answer += 1
print(answer)


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


def is_prime(k):
	small = [2]
	if k in small:
		return True
	if k % 2 == 0:
		return False
	odd = k - 1
	e = 0
	while odd % 2 == 0:
		e += 1
		odd = odd // 2
	for p in small:
		num = pow(p, odd, k)
		check = False
		if num == 1 or num == k - 1:
			continue
		for i in range(e):
			num = pow(num, 2, k)
			if num == k - 1:
				check = True
				break
			if num == 1:
				return False
		if not check and num != 1:
			return False
	return True
d2 = {'0': '2', '1': '2', '2': '2', '3': '3', '4': '5', '5': '5', '6': '7', '7': '7', '8': '2', '9': '2', '10': '2'}
d3 = {'0': '2', '1': '2', '2': '3', '3': '5', '4': '5', '5': '7', '6': '7', '7': '2', '8': '2', '9': '2', '10': '2'}
primes = [2, 3, 5, 7]

def next_num(n):
	s = str(n)
	s2 = ''
	carry = False
	if int(s[-1]) >= 7:
		carry = True
		s2 = '3'
	elif int(s[-1]) < 3:
		s2 = '3'
	else:
		s2 = '7'
	for i in range(2, len(s) + 1):
		letter = s[-i]
		if carry:
			s2 = d3[letter] + s2
			if int(letter) < 7:
				carry = False
		else:
			s2 = d2[letter] + s2
	if carry:
		s2 = '2' + s2
	return int(s2)

def other_next_num(s):
	s = s[::-1]
	s2 = ''
	carry = False
	if int(s[0]) >= 7:
		carry = True
		s2 = '2'
	else:
		s2 = d3[s[0]]
	for letter in s[1:]:
		if carry:
			s2 = d2[str(int(letter) + 1)] + s2
			if int(letter) < 7:
				carry = False
		else:
			s2 = d2[letter] + s2
			if int(letter) > 7:
				carry = True
	if carry:
		s2 = '2' + s2
	return s2

def find_start(n):
	s = str(n)
	mid = False
	s2 = ''
	s3 = ''
	for letter in s:
		if mid:
			s2 = s2 + '2'
		else:
			i = int(letter)
			if i not in primes:
				mid = True
				s2 = d2[str(i + 1)]
				if len(s3) > 1 and i > 7:
					s3 = other_next_num(s3)
				elif len(s3) == 1 and i > 7:
					s3 = d2[str(int(s3) + 1)]
				elif int(letter) > 7:
					s3 = '2'
			else:
				s3 += letter
	ans = s3 + s2
	return int(ans)
firstLast = input().split()
first = int(firstLast[0])
last = int(firstLast[1])
count = 0
if 2 >= first and 2 <= last:
	count += 1
if 5 >= first and 5 <= last:
	count += 1
s = str(first)
if '0' in s or '1' in s or '4' in s or ('6' in s) or ('8' in s) or ('9' in s) or (s == '2') or (s == '5'):
	if first < 3:
		first = 3
	elif first > 3 and first < 7:
		first = 7
	elif first < 10 and first > 7:
		first = 23
	else:
		first = find_start(first)
while first <= last:
	if is_prime(first):
		count += 1
	first = next_num(first)
print(count)


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


from random import randrange
import sys

def miller_rabin(n, k=10):
	if n == 2 or n == 3 or n == 5 or (n == 7):
		return True
	if n % 2 == 0 or n % 5 == 0:
		return False

	def check(a, s, d, n):
		x = pow(a, d, n)
		if x == 1:
			return True
		for i in range(s - 1):
			if x == n - 1:
				return True
			x = pow(x, 2, n)
		return x == n - 1
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for i in range(k):
		a = randrange(2, n - 1)
		if not check(a, s, d, n):
			return False
	return True

def to4(q):
	digits = [2, 3, 5, 7]
	q += 1
	e = 1
	n = 0
	while q != 0:
		(q, r) = divmod(q - 1, 4)
		n += e * digits[r]
		e *= 10
	return n

def from4(s):
	digits = [0, 0, 0, 1, 0, 2, 0, 3, 0, 0]
	n = -1
	for d in str(s):
		d = digits[int(d)]
		n = 4 * (n + 1) + d
	return n
(start, end) = map(int, input().split())
carry = False
start4 = -1
for d in str(start):
	if carry:
		d = 3
	else:
		d = int(d)
		if d >= 7:
			d = 3
		elif d >= 5:
			d = 2
		elif d >= 3:
			d = 1
		elif d == 2:
			d = 0
		else:
			d = 3
			carry = True
			start4 -= 1
	start4 = 4 * (start4 + 1) + d
if start4 == -1:
	start4 = 0
answer = 0
i = start4
while True:
	n = to4(i)
	i += 1
	if n > end:
		break
	if n < start:
		continue
	if miller_rabin(n):
		answer += 1
print(answer)


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


import math
import os
import random
import re
import sys
import itertools
(n, m) = map(int, input().strip().split(' '))

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


def is_witness(a, d, s, n):
	x = pow(a, d, n)
	if x == 1 or x == n - 1:
		return False
	while s > 1:
		s -= 1
		x = x * x % n
		if x == n - 1:
			return False
	return True
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}

def is_prime(n):
	if n < 2:
		return False
	if n in primes:
		return True
	(d, s) = (n - 1, 0)
	while d % 2 == 0:
		d //= 2
		s += 1
	for a in primes:
		if is_witness(a, d, s, n):
			return False
	return True

def b10to4(n, d):
	x = 0
	p = 1
	while n:
		x += p * (n % 4)
		n //= 4
		p *= 10
	x = str(x).zfill(d)[-d:]
	return int(x.replace('3', '7').replace('2', '5').replace('1', '3').replace('0', '2'))

def is2357(n, l):
	for i in range(l):
		if n[i] not in {'2', '3', '5', '7'}:
			return False
	return True

def make2357(n, l):
	n = str(n)
	if is2357(n, l):
		return n
	for i in range(l):
		if n[i] in {'2', '3', '5', '7'}:
			continue
		if n[i] in {'0', '1'}:
			return n[:i] + '2' * (l - i)
		if n[i] == '4':
			return n[:i] + '5' + '2' * (l - i - 1)
		if n[i] == '6':
			return n[:i] + '7' + '2' * (l - i - 1)
		if n[i] in {'8', '9'}:
			while i:
				i -= 1
				if n[i] == '7':
					continue
				if n[i] == '2':
					return n[:i] + '3' + '2' * (l - i - 1)
				if n[i] == '3':
					return n[:i] + '5' + '2' * (l - i - 1)
				if n[i] == '5':
					return n[:i] + '7' + '2' * (l - i - 1)
			break
	return '2' * (l + 1)

def b4to10(n):
	n = n.replace('2', '0').replace('3', '1').replace('5', '2').replace('7', '3')
	return int(n, 4)
(a, b) = list(map(int, input().strip().split()))
(la, lb) = (len(str(a)), len(str(b)))
ans = 0
s = make2357(a, la)
if len(s) == la:
	s = b4to10(s)
	for i in range(s, 4 ** la):
		n = b10to4(i, la)
		if n > b:
			break
		if is_prime(n):
			ans += 1
for d in range(la + 1, lb + 1):
	for i in range(4 ** d):
		n = b10to4(i, d)
		if n > b:
			break
		if is_prime(n):
			ans += 1
print(ans)


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


import math
import os
import random
import re
import sys
import itertools
firstLast = input().split()
first = int(firstLast[0])
last = int(firstLast[1])

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
m = last
n = first
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


from random import randrange
import sys

def miller_rabin(n, k=10):
	if n == 2 or n == 3 or n == 5 or (n == 7):
		return True
	if n % 2 == 0 or n % 5 == 0:
		return False

	def check(a, s, d, n):
		x = pow(a, d, n)
		if x == 1:
			return True
		for i in range(s - 1):
			if x == n - 1:
				return True
			x = pow(x, 2, n)
		return x == n - 1
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for i in range(k):
		a = randrange(2, n - 1)
		if not check(a, s, d, n):
			return False
	return True

def to4(q):
	digits = [2, 3, 5, 7]
	q += 1
	e = 1
	n = 0
	while q != 0:
		(q, r) = divmod(q - 1, 4)
		n += e * digits[r]
		e *= 10
	return n

def from4(s):
	digits = [0, 0, 0, 1, 0, 2, 0, 3, 0, 0]
	n = -1
	for d in str(s):
		d = digits[int(d)]
		n = 4 * (n + 1) + d
	return n
(start, end) = map(int, input().split())
carry = False
start4 = -1
for d in str(start):
	if carry:
		d = 3
	else:
		d = int(d)
		if d >= 7:
			d = 3
		elif d >= 5:
			d = 2
		elif d >= 3:
			d = 1
		elif d == 2:
			d = 0
		else:
			d = 3
			carry = True
			start4 -= 1
	start4 = 4 * (start4 + 1) + d
if start4 == -1:
	start4 = 0
answer = 0
i = start4
while True:
	n = to4(i)
	i += 1
	if n > end:
		break
	if n < start:
		continue
	if miller_rabin(n):
		answer += 1
print(answer)


import math
import os
import random
import re
import sys

def nextmp(prime):
	digs = [2, 3, 5, 7]
	output = 0
	pwr10 = 1
	while prime > 0:
		output += pwr10 * digs[prime % 4]
		prime //= 4
		pwr10 *= 10
	return output

def nextmps(prime):
	dicts = {'2': 0, '3': 1, '5': 2, '7': 3}
	chars = ['2', '3', '5', '7']
	digit = 0
	while digit < len(prime) and prime[digit] == '7':
		prime[digit] = '2'
		digit += 1
	if digit < len(prime):
		prime[digit] = chars[dicts[prime[digit]] + 1]
	else:
		prime.append('2')
	if len(prime) > 1:
		if prime[0] == '2':
			prime[0] = '3'
		elif prime[0] == '5':
			prime[0] = '7'
	return prime

def prevmps(prime):
	dicts = {'2': 0, '3': 1, '5': 2, '7': 3}
	chars = ['2', '3', '5', '7']
	digit = 0
	if prime[0] == '3':
		prime[0] = '2'
	elif prime[0] == '7':
		prime[0] = '3'
	while digit < len(prime) and prime[digit] == '2':
		prime[digit] = '7'
		digit += 1
	if digit < len(prime):
		if digit > 0:
			prime[digit] = chars[dicts[prime[digit]] - 1]
	else:
		prime.pop()
	return prime

def get_higher_mp(n):
	chars = ['2', '3', '5', '7']
	decimal = []
	while n > 0:
		last = chr(n % 10 + ord('0'))
		decimal.append(last)
		n //= 10
	dig = len(decimal) - 1
	mp = list(decimal)
	while dig >= 0 and mp[dig] in chars:
		dig -= 1
	if dig >= 0:
		if mp[dig] in ['8', '9']:
			mp[dig] = '7'
			while dig > 0:
				dig -= 1
				mp[dig] = '7'
			return nextmps(mp)
		elif mp[dig] == '6':
			mp[dig] = '7'
		elif mp[dig] == '4':
			mp[dig] = '5'
		else:
			mp[dig] = '2'
		while dig > 0:
			dig -= 1
			mp[dig] = '2'
	if len(mp) > 1:
		if mp[0] == '2':
			mp[0] = '3'
		elif mp[0] == '5':
			mp[0] = '7'
	return mp

def get_lower_mp(n):
	chars = ['2', '3', '5', '7']
	decimal = []
	while n > 0:
		last = chr(n % 10 + ord('0'))
		decimal.append(last)
		n //= 10
	dig = len(decimal) - 1
	mp = list(decimal)
	while dig >= 0 and mp[dig] in chars:
		dig -= 1
	if dig >= 0:
		if mp[dig] in ['0', '1']:
			mp[dig] = '2'
			while dig > 0:
				dig -= 1
				mp[dig] = '2'
			return prevmps(mp)
		elif mp[dig] in ['8', '9']:
			mp[dig] = '7'
		elif mp[dig] == '6':
			mp[dig] = '5'
		else:
			mp[dig] = '3'
		while dig > 0:
			dig -= 1
			mp[dig] = '7'
	if len(mp) > 1:
		if mp[0] == '2':
			return prevmps(mp)
		elif mp[0] == '5':
			mp[0] = '3'
	return mp

def pwr_mod(base, pwr, modb):
	out = 1
	while pwr > 0:
		if pwr % 2 == 1:
			out = out * base % modb
		base = base * base % modb
		pwr = pwr >> 1
	return out

def miller_rabin(pr):
	prlist = [2, 3, 5, 7, 17, 23, 31, 41, 47, 71, 73, 79, 89]
	for pp in prlist:
		if pp == pr:
			return True
		if pr % pp == 0:
			return False
	if pr < 2047:
		bases = [2]
	elif pr < 1373653:
		bases = [2, 3]
	elif pr < 25326001:
		bases = [2, 3, 5]
	elif pr < 3215031751:
		bases = [2, 3, 5, 7]
	elif pr < 2152302898747:
		bases = [2, 3, 5, 7, 11]
	elif pr < 3474749660383:
		bases = [2, 3, 5, 7, 11, 13]
	else:
		bases = [2, 3, 5, 7, 11, 13, 17]
	d = pr - 1 >> 1
	r = 1
	while d % 2 == 0:
		r += 1
		d = d >> 1
	for bs in bases:
		if bs >= pr:
			break
		maybeprime = False
		x = pwr_mod(bs, d, pr)
		if x == 1 or x == pr - 1:
			continue
		for rr in range(r - 1):
			x = x * x % pr
			if x == pr - 1:
				maybeprime = True
				break
		if maybeprime:
			continue
		return False
	return True

def isprime(themp):
	nbr = 0
	for dig in range(len(themp) - 1, -1, -1):
		nbr = 10 * nbr + ord(themp[dig]) - 48
	isit = miller_rabin(nbr)
	return isit
firstLast = input().split()
first = int(firstLast[0])
last = int(firstLast[1])
mp = ['7', '7', '7']
firstmp = get_higher_mp(first)
lastmp = get_lower_mp(last)
count = 0
themp = firstmp
while True:
	if isprime(themp):
		count += 1
	if themp == lastmp:
		break
	themp = nextmps(themp)
print(count)


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


import math
import os
import random
import re
import sys
maxprime = 100000
isprime = [True] * maxprime
primelist = []
numprimes = 0
for i in range(2, maxprime):
	if isprime[i]:
		primelist.append(i)
		numprimes += 1
		for j in range(i * i, maxprime, i):
			isprime[j] = False

def isitprime(n):
	for p in primelist[:10]:
		if p == n:
			return True
		elif n % p == 0:
			return False
		elif pow(p, n - 1, n) != 1:
			return False
	return True
firstLast = input().split()
first = int(firstLast[0])
last = int(firstLast[1])
toprint = 0
openings = [0]
for i in range(16, 0, -1):
	nextopenings = []
	if first < pow(10, i):
		nextopenings.append(0)
	for x in openings:
		for dig in [2, 3, 5, 7]:
			if not (last // pow(10, i) < x or first // pow(10, i) > x):
				nextopenings.append(10 * x + dig)
	openings = nextopenings
toprint = 0
for n in openings:
	if isitprime(n):
		toprint += 1
print(toprint)


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


from random import randrange
import sys

def miller_rabin(n, k=10):
	if n == 2 or n == 3 or n == 5 or (n == 7):
		return True
	if n % 2 == 0 or n % 5 == 0:
		return False

	def check(a, s, d, n):
		x = pow(a, d, n)
		if x == 1:
			return True
		for i in range(s - 1):
			if x == n - 1:
				return True
			x = pow(x, 2, n)
		return x == n - 1
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for i in range(k):
		a = randrange(2, n - 1)
		if not check(a, s, d, n):
			return False
	return True

def to4(q):
	digits = [2, 3, 5, 7]
	q += 1
	e = 1
	n = 0
	while q != 0:
		(q, r) = divmod(q - 1, 4)
		n += e * digits[r]
		e *= 10
	return n

def from4(s):
	digits = [0, 0, 0, 1, 0, 2, 0, 3, 0, 0]
	n = -1
	for d in str(s):
		d = digits[int(d)]
		n = 4 * (n + 1) + d
	return n
(start, end) = map(int, input().split())
carry = False
start4 = -1
for d in str(start):
	if carry:
		d = 3
	else:
		d = int(d)
		if d >= 7:
			d = 3
		elif d >= 5:
			d = 2
		elif d >= 3:
			d = 1
		elif d == 2:
			d = 0
		else:
			d = 3
			carry = True
			start4 -= 1
	start4 = 4 * (start4 + 1) + d
if start4 == -1:
	start4 = 0
answer = 0
i = start4
while True:
	n = to4(i)
	i += 1
	if n > end:
		break
	if n < start:
		continue
	if miller_rabin(n):
		answer += 1
print(answer)


import math
import os
import random
import re
import sys
import bisect

def miller_test(n):
	if n < 2047:
		a_list = [2]
	elif n < 1373653:
		a_list = [2, 3]
	elif n < 25326001:
		a_list = [2, 3, 5]
	elif n < 3215031751:
		a_list = [2, 3, 5, 7]
	else:
		a_list = [2, 3, 5, 7, 11]
	d = n - 1
	r = 0
	while d // 2 == 0:
		d = d // 2
		r += 1
	for a in a_list:
		x = pow(a, d, n)
		if x == 1 or x == n - 1:
			continue
		cont_flag = False
		for i in range(r - 1):
			x = pow(x, 2, n)
			if x == n - 1:
				cont_flag = True
				break
		if not cont_flag:
			return False
	return True

def fermat_little(n):
	if n <= 4:
		return n == 2 or n == 3
	for i in range(5):
		a = random.randint(2, n - 2)
		if pow(a, n - 1, n) != 1:
			return False
	return True

def sieve_for_primes_to(n):
	size = n // 2
	sieve = [1] * size
	limit = int(n ** 0.5)
	for i in range(1, limit):
		if sieve[i]:
			val = 2 * i + 1
			tmp = (size - 1 - i) // val
			sieve[i + val::val] = [0] * tmp
	return [2] + [i * 2 + 1 for (i, v) in enumerate(sieve) if v and i > 0]

def check_prime(n, all_primes):
	last = bisect.bisect_right(all_primes, math.sqrt(n))
	for p in all_primes[:last + 1]:
		if n // p == 0:
			return False
	return True

def numberToBase(n, b):
	if n == 0:
		return [0]
	digits = []
	while n:
		digits.append(int(n % b))
		n //= b
	return digits[::-1]

def numberToPrimeDigits(n, b, f_len, p_digits, prefix):
	n_b = numberToBase(n, b)
	first = str(p_digits[0]) * (f_len - len(n_b))
	res = prefix + first + ''.join([str(p_digits[d]) for d in n_b])
	return int(res)

def solve(first, last):
	p_digits = [2, 3, 5, 7]
	f_s = str(first)
	l_s = str(last)
	f_len = len(f_s)
	l_len = len(l_s)
	if l_len > 9:
		for d in f_s[:-10]:
			if int(d) not in p_digits:
				return 0
		d = int(l_s[-10])
		d_f = int(f_s[-10])
		if l_len == 10 and d == 1:
			l_s = '7' * 9
			last = int(l_s)
		elif d == 0:
			return 0
		elif d == d_f:
			pass
		elif d not in p_digits and d - 1 not in p_digits:
			return 0
		elif d in p_digits:
			f_s = l_s[:-9] + '2' * 9
			first = int(f_s)
		else:
			l_s = l_s[:-10] + str(d - 1) + '7' * 9
			last = int(l_s)
	if last < first:
		return 0
	f_len = len(f_s)
	l_len = len(l_s)
	count = 0
	if 2 >= first:
		count += 1
	break_flag = False
	while f_len <= l_len and (not break_flag):
		prefix = ''
		if f_len > 9:
			prefix = str(first)[:-9]
		rem_len = min(f_len, 9)
		for i in range(1, 4 ** rem_len):
			num = numberToPrimeDigits(i, 4, rem_len, p_digits, prefix)
			if num > last:
				break_flag = True
				break
			if num < first or str(num)[-1] == 2:
				continue
			if fermat_little(num):
				count += 1
		f_len += 1
	return count
firstLast = input().split()
first = int(firstLast[0])
last = int(firstLast[1])
res = solve(first, last)
print(res)


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


import math
import os
import random
import re
import sys
(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


import math as m
import os
import random
import re
import sys
import itertools
import random
import re
import sys
first_multiple_input = input().rstrip().split()
n = int(first_multiple_input[0])
m = int(first_multiple_input[1])

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


import math
import os
import random
import re
import sys
(n, m) = map(int, input().strip().split(' '))
import itertools
import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	a = 2 + random.randint(1, n - 4)
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n, k):
	if n <= 1 or n == 4:
		return False
	if n <= 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return False
	return True
x = ['2', '3', '5', '7']
P = []
k = 4
b = ''
if len(str(n)) > 9:
	i = 0
	while i < len(str(n)) and str(n)[i] == str(m)[i]:
		b += str(n)[i]
		i += 1
c = len(b)
for i in range(len(str(n)), len(str(m)) + 1):
	L = [p for p in itertools.product(x, repeat=i - c)]
	for j in range(len(L)):
		a = int(b + ''.join(L[j]))
		if a > m:
			break
		if a > n and isPrime(a, k):
			P.append(a)
print(len(P))


from random import randrange
import sys

def miller_rabin(n, k=10):
	if n == 2 or n == 3 or n == 5 or (n == 7):
		return True
	if n % 2 == 0 or n % 5 == 0:
		return False

	def check(a, s, d, n):
		x = pow(a, d, n)
		if x == 1:
			return True
		for i in range(s - 1):
			if x == n - 1:
				return True
			x = pow(x, 2, n)
		return x == n - 1
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for i in range(k):
		a = randrange(2, n - 1)
		if not check(a, s, d, n):
			return False
	return True

def to4(q):
	digits = [2, 3, 5, 7]
	q += 1
	e = 1
	n = 0
	while q != 0:
		(q, r) = divmod(q - 1, 4)
		n += e * digits[r]
		e *= 10
	return n

def from4(s):
	digits = [0, 0, 0, 1, 0, 2, 0, 3, 0, 0]
	n = -1
	for d in str(s):
		d = digits[int(d)]
		n = 4 * (n + 1) + d
	return n
(start, end) = map(int, input().split())
carry = False
start4 = -1
for d in str(start):
	if carry:
		d = 3
	else:
		d = int(d)
		if d >= 7:
			d = 3
		elif d >= 5:
			d = 2
		elif d >= 3:
			d = 1
		elif d == 2:
			d = 0
		else:
			d = 3
			carry = True
			start4 -= 1
	start4 = 4 * (start4 + 1) + d
if start4 == -1:
	start4 = 0
answer = 0
i = start4
while True:
	n = to4(i)
	i += 1
	if n > end:
		break
	if n < start:
		continue
	if miller_rabin(n):
		answer += 1
print(answer)