def prime_pair(a,b):
    a_b = a * 10 ** int(log10(b)+1) + b
    if not is_prime(a_b):
        return False

    b_a = b * 10 ** int(log10(a)+1) + a
    if not is_prime(b_a):
        return False
    return True

def truncatable(p):
    s = str(p)
    l = len(s)
    for i in range(1, l):
        if not is_prime(int(s[i:])):
            return False
        if not is_prime(int(s[:i])):
            return False
    return True

def truncatable_prime(n):
    str_n = str(n)
    for i in range(len(str_n)):
        right = int(str_n[:i+1])
        left = int(str_n[i:])
        if not is_prime(right) or not is_prime(left):
            return False

    return True

def solve():
    for i in range(35,10000,2):
        if is_prime(i):
            continue
        else:
            found_one = 0
            for x in range(1,int(math.sqrt(i)+1)):
                if is_prime(i-2*(x**2)):
                    found_one = 1
            if not found_one:
                return i

def is_prime_truncatable(n):
	right = n
	while num_digits(right) > 0:
		if not is_prime(right):
			return False
		right = rtrunc(right)
	left = n
	while num_digits(left) > 0:
		if not is_prime(left):
			return False
		left = ltrunc(left)
	return True

def truncatable(num):
    num = str(num)
    temp_num = str(num)
    for i in range(0, len(num) - 1):
        temp_num = temp_num[1:]
        if not utils.is_prime(int(temp_num)):
            return False

    for i in range(0, len(num) - 1):
        num = num[:-1]
        if not utils.is_prime(int(num)):
            return False

    return True

def prime_series_length(a, b):
	"""Find the number of primes for consecutive n, starting with n=0,
	for quad(n, a, b)."""
	n = 0
	while is_prime(quad(n, a, b)):
		n += 1
	return n

def count_primes(fun):
    counter = 0
    for n in count():
        if is_prime(fun(n)):
            counter += 1
        else:
            return counter

def generate_shadows(k, s, p, ms, check=True):
    ms.sort()
    r = len(ms)
    #check if values meet requirements
    if check:
        if s > len(ms):
            raise Exception("Threshold cannot exceed the number of shadows.")
        if not utils.is_prime(p):
            raise Exception("p is not prime")
        for m in ms:
            if not utils.is_rel_prime(m, ms):
                raise Exception("The moduli must be pairwise relatively prime.")

    M = 1
    for i in range(0, s):
        M *= ms[i]
    largest = p
    for i in range(0, s-1):
        largest *= ms[r-1-i]
    if M <= largest:
        raise Exception("The product of the smallest s moduli must be greater than the product of the s-1 largest moduli times p.")

    #print "M = ", M
    t = randint(0, int(M/p))
    k0 = k + t*p 
    #print k0

    shadows = []
    for m in ms:
        shadows.append(k0 % m)

    return t, shadows

def prime(n):
    if n not in prime_cache:
        if n > len(sieve):
            prime_cache[n] = is_prime(n)
        else:
            prime_cache[n] = sieve[n]
    return prime_cache[n]

def num_divisors(num):
    primes = utils.sieve_of_eratosthenes(int(math.ceil(math.sqrt(num))))
    factors = []
    prime_counter = 0
    while num != 1:
        if prime_counter > len(primes) - 1:
            if num % 2 != 0 and num > 3 and utils.is_prime(num, 10):
                factors.append(num)
                break
            else:
                print("fail")
                break
        if num % primes[prime_counter] == 0:
            num /= primes[prime_counter]
            factors.append(primes[prime_counter])
        else:
            prime_counter += 1

    c = Counter(factors)

    product = 1

    for key, value in c.iteritems():
        value += 1
        product *= value

    return product

def run():
	to_proc = []
	for prime in primes(1000,10000):
		to_proc.append(prime)
	to_proc.sort()
	permutations = []
	for i in to_proc[:]:
		if len(permutations) == 2:
			break
		for j in xrange(1, (10000-i)/2):
			second = str(i+j)
			if is_prime(i+j) and is_permutation(str(i), second):
				third = i+j+j
				if is_prime(third) and is_permutation(second, str(third)):
					permutations.append((i,i+j,i+j+j))
	print permutations

def isStrongRightTruncatableHarshadPrime(n):
    if not is_prime(n):
        return False
    else:
        s = str(n)
        t = int(s[:len(s)-1])
        return isStrongHarshad(t)

def main():
    # A prime n > 10 must end in one of these numbers.
    possible_prime_suffix = frozenset(('1', '3', '7', '9'))
    highest_prime = 0

    # Progressivly create a smaller string of candidate numbers by
    # slicing the base str.
    str_num_base = '123456789'
    for x in range(9, 0, -1):
        str_num = str_num_base[:x]
        # Skip suffixes that are greater than the slice index, This stops
        # use getting possible values like 1239 which clearly isnt pandigital
        for suf in possible_prime_suffix:
            if int(suf) > x:
                continue
            # Remove the suffix from the number.
            suffed_str_num = str_num.replace(suf, '')
            # Get permutations of the remaining digits.
            # Append the suffix and check if the result is prime.
            for perm in permutations(suffed_str_num, x-1):
                i = int(''.join(perm) + suf)
                if is_prime(i):
                    # Store the prime but continue for the same iteration of x
                    # since its possible that smaller prime was given back from
                    # permutations first.
                    if i > highest_prime:
                        highest_prime = i

        if highest_prime != 0:
            return highest_prime

def main():
    D = 10
    digits = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
    total = 0

    for d in digits:
        for n in range(D-1, 0, -1):
            if d == 0 and n == D-1:
                continue
            S = 0
            for indexes in combinations(range(D), n):
                repeating = [d if i in indexes else None for i in range(D)]

                for others in product(digits[:d] + digits[d+1:], repeat=D-n):
                    others = iter(others)
                    num = [next(others) if x is None else x for x in repeating]

                    if num[0] and num[-1] in {1, 3, 7, 9} and sum(num) % 3:
                        x = reduce(lambda x, y: x*10 + y, num)
                        if is_prime(x):
                            S += x
            if S:
                total += S
                break
    return total

def primes(n):
    for p in range(2, n):
        if p in known_primes:
            yield p
        elif is_prime(p):
            known_primes[p] = None
            yield p

def is_prime_cached(n):
    try:
        return prime_cache[n]
    except KeyError:
        p = is_prime(n)
        prime_cache[n] = p
        return p

 def test_is_prime(self):
     self.assertTrue(is_prime(2))
     self.assertTrue(is_prime(3))
     self.assertTrue(is_prime(5))
     self.assertTrue(is_prime(109))
     self.assertTrue(is_prime(673))
     self.assertFalse(is_prime(1))
     self.assertFalse(is_prime(15))
     self.assertFalse(is_prime(999))

def main():
    start_permutation = [9, 8, 7, 6, 5, 4, 3, 2, 1]
    while len(start_permutation) > 1:
        for i in permutations(start_permutation):
            if utils.is_prime(to_int(i)):
                print to_int(i)
                return
        start_permutation = start_permutation[1:]

def run():
    i = 1
    count = 0
    while count < 10091:
        i += 1
        if utils.is_prime(i):
            count += 1
    print i