import math

class sieve:
	def __init__(self, limit):
		self.limit = limit
		self.number_list = [False] + [True]*(self.limit-1)
		self.list_len = len(self.number_list)

	def next_prime(self, i):
		x = i+1
		while(x <= self.list_len):
			if self.number_list[x-1] == True:
				break
			x += 1
		return x

	def primes(self):
		i = 2
		while(i*i <= self.list_len):
			x = i*i
			while(x <= self.list_len):
				self.number_list[x-1] = False
				x += i
			i = self.next_prime(i)

		primeset = set()
		for i in xrange(1, self.limit+1):
			if self.number_list[i-1]:
				primeset.add(i)
		return primeset

class pandigital:
	# create n-digit pandigital numbers
	def __init__(self, start, end):
		self.digits = set()
		for d in range(start, end+1):
			self.digits.add(d)
	
	# return set of digits that are not in x
	def missing(self, x):
		d = set()
		while x > 0:
			d.add(x % 10)
			x /= 10
		return self.digits - d

	def numbers(self, r):
		result = set()
		result |= self.digits
		for i in range(2, r):
			new = set()
			for x in result:
				for y in self.missing(x):
					new.add(x*10 + y)
			result |= new
		return result

def ggt(a, b): # Stein's algorithm
	k = 0
	t = 0
	while a&1==0 and b&1==0:
		a = a>>1
		b = b>>1
		k += 1
	if a&1==1:
		t = -b
	else:
		t = a
	while t != 0:
		while t&1==0:
			t = t>>1
		if t>0:
			a = t
		else:
			b = -t
		t = a - b
	return a*(1<<k)

def composite(n): # check if n = c^b
	primes = sieve(int(math.sqrt(n))+1).primes()
	for c in primes:
		number = c
		while number < n:
			number *= c
		if number == n:
			return True
	return False

def order(n, r):
	res = n % r
	k = 1
	while res != 1:
		res = (res * n) % r
		k += 1
	return k

def phi(x):
	primes = sieve(x+1).primes()
	product = x
	for p in primes:
		if x % p != 0:
			continue
		product *= (1 - 1.0/p)
	return int(product)
		

def prime_test(n): # aks test
	if composite(n):
		return False

	logn = math.log(n, 2)
	o = 0
	r = 0
	while o <= logn:
		r += 1
		o = order(n, r)

	a = 1
	while a <= r:
		g = ggt(a, n)
		if g < n and g > 1:
			return False
		a += 1

	if n <= r*r:
		return True

	#for a in xrange(1, math.floor(math.sqrt(phi(r))*logn)):
	#	# TODO if math.pow(x+a, n) != 
	
	return True

def permutation(p, q): # checks whether p is a permuation of q
	digits_p = [0]*10
	digits_q = [0]*10
	while p > 0:
		digit = p % 10
		digits_p[digit] += 1
		p /= 10
	while q > 0:
		digit = q % 10
		digits_q[digit] += 1
		q /= 10
	return digits_p == digits_q