Do you remember how Kai constructed the word "eternity" using pieces of ice as components?

Little Sheldon plays with pieces of ice, each piece has exactly one digit between 0 and 9. He wants to construct his favourite number t. He realized that digits 6 and 9 are very similar, so he can rotate piece of ice with 6 to use as 9 (and vice versa). Similary, 2 and 5 work the same. There is no other pair of digits with similar effect. He called this effect "Digital Mimicry".

Sheldon favourite number is t. He wants to have as many instances of t as possible. How many instances he can construct using the given sequence of ice pieces. He can use any piece at most once. 


-----Input-----

The first line contains integer t (1 ≤ t ≤ 10000). The second line contains the sequence of digits on the pieces. The length of line is equal to the number of pieces and between 1 and 200, inclusive. It contains digits between 0 and 9.


-----Output-----

Print the required number of instances.


-----Examples-----
Input
42
23454

Output
2

Input
169
12118999

Output
1



-----Note-----

This problem contains very weak pretests.

Difficulty: MEDIUM
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
t = input()
s = input()
s = list(s)
n = len(s)
copies = 0
x = t.count('6') + t.count('9')
y = s.count('6') + s.count('9')
a = t.count('2') + t.count('5')
b = s.count('2') + s.count('5')
if x == 0 and a == 0:
	copies = 100
elif x == 0:
	copies = b // a
elif a == 0:
	copies = y // x
else:
	copies = min(y // x, b // a)
for j in range(0, 10):
	i = str(j)
	if i == '6' or i == '9' or i == '2' or (i == '5'):
		continue
	x = t.count(i)
	if x == 0:
		continue
	y = s.count(i)
	copies = min(copies, y // x)
print(copies)


import sys

def solve():
	first = list(input())
	second = list(input())
	first = map(int, first)
	second = map(int, second)
	count = [0] * 10
	for i in first:
		count[m(i)] += 1
	total = [0] * 10
	for i in second:
		total[m(i)] += 1
	res = 0
	while True:
		for i in range(10):
			total[i] -= count[i]
		for i in range(10):
			if total[i] < 0:
				return res
		res += 1
	return res

def m(c):
	if c == 9:
		return 6
	if c == 5:
		return 2
	return c
if sys.hexversion == 50594544:
	sys.stdin = open('test.txt')
print(solve())


t = int(input())
s = input()
q = {'0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '6': 0, '7': 0, '8': 0}
for d in s:
	if d == '5':
		q['2'] += 1
	elif d == '9':
		q['6'] += 1
	else:
		q[d] += 1
p = {'0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '6': 0, '7': 0, '8': 0}
while t != 0:
	d = str(t % 10)
	if d == '5':
		p['2'] += 1
	elif d == '9':
		p['6'] += 1
	else:
		p[d] += 1
	t //= 10
c = len(s)
for d in list(p.keys()):
	if p[d] != 0:
		c = min(c, q[d] // p[d])
print(c)


req_arr = [int(x) for x in input().strip()]
arr = [int(x) for x in input().strip()]
required_list = [0] * 10
num_list = [0] * 10
for i in req_arr:
	if i == 5:
		required_list[2] += 1
	elif i == 9:
		required_list[6] += 1
	else:
		required_list[i] += 1
for i in arr:
	if i == 5:
		num_list[2] += 1
	elif i == 9:
		num_list[6] += 1
	else:
		num_list[i] += 1
ans = len(arr)
for (i, j) in enumerate(required_list):
	if j > 0:
		ans = min(ans, int(num_list[i] / j))
print(ans)


t = input().replace('5', '2').replace('9', '6')
s = input().replace('5', '2').replace('9', '6')
res = 10 ** 100
for i in t:
	res = min(res, s.count(i) // t.count(i))
print(res)


def solution():
	number = input()
	book = {}
	book_of_repeats = {}
	for i in number:
		intermidiate = i
		if intermidiate == '5':
			intermidiate = '2'
		elif intermidiate == '9':
			intermidiate = '6'
		book_of_repeats[intermidiate] = 0
		if intermidiate in book:
			book[intermidiate] += 1
		else:
			book[intermidiate] = 1
	cubs = input()
	for i in cubs:
		intermidiate = i
		if intermidiate == '5':
			intermidiate = '2'
		elif intermidiate == '9':
			intermidiate = '6'
		if intermidiate in book_of_repeats:
			book_of_repeats[intermidiate] += 1
	result = len(cubs) // len(number)
	for i in book:
		intermidiate = book_of_repeats[i] // book[i]
		if intermidiate < result:
			result = intermidiate
	print(result)

def to_mixed_frac(first, second):
	while True:
		for i in range(2, first + 1):
			if first % i == 0 and second % i == 0:
				first //= i
				second //= i
				break
		else:
			break
	return str(first) + '/' + str(second)

def array_to_int(array):
	for i in range(len(array)):
		array[i] = int(array[i])
	return array

def join0(array):
	result = ''
	for i in array:
		result += str(i)
	return result
solution()


t = [*map(int, input())]
s = [*map(int, input())]
d = {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 6: 0, 7: 0, 8: 0}
di = {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 6: 0, 7: 0, 8: 0}
for (i, x) in enumerate(t):
	if x == 6 or x == 9:
		d[6] += 1
	elif x == 2 or x == 5:
		d[2] += 1
	else:
		d[x] += 1
for (i, x) in enumerate(s):
	if x == 6 or x == 9:
		di[6] += 1
	elif x == 2 or x == 5:
		di[2] += 1
	else:
		di[x] += 1
res = 10000000000000000000000000
for (i, x) in enumerate(d):
	if d[x] > 0:
		res = min(res, di[x] // d[x])
print(res)


a = input()
b = input()
d = {}
for e in b:
	if e == '9':
		e = '6'
	if e == '5':
		e = '2'
	if e in d:
		d[e] = d[e] + 1
	else:
		d[e] = 1
n = {}
for e in a:
	if e == '9':
		e = '6'
	if e == '5':
		e = '2'
	if e in n:
		n[e] += 1
	else:
		n[e] = 1
result = 10000000
for e in n:
	if e not in d:
		result = 0
		break
	else:
		temp_result = int(d[e] / n[e])
		if temp_result < result:
			result = temp_result
print(result)


(t, a) = (input(), input())
(t, a) = (t.replace('5', '2'), a.replace('5', '2'))
(t, a) = (t.replace('9', '6'), a.replace('9', '6'))
ac = dict().fromkeys([i for i in a], 0)
for i in a:
	ac[i] += 1
print(min([ac[i] // t.count(i) for i in t]))


s = input()
t = input()
a = [0] * 10
b = [0] * 10
for i in range(len(s)):
	if s[i] == '5':
		a[2] += 1
	elif s[i] == '9':
		a[6] += 1
	else:
		a[int(s[i])] += 1
for i in range(len(t)):
	if t[i] == '5':
		b[2] += 1
	elif t[i] == '9':
		b[6] += 1
	else:
		b[int(t[i])] += 1
ans = 10 ** 9
for i in range(10):
	if a[i] != 0:
		ans = min(ans, b[i] // a[i])
print(ans)


from collections import defaultdict
import math
t = input()
s = input()
tomake = defaultdict(lambda : 0)
for i in t:
	if i == '5':
		tomake['2'] += 1
	elif i == '9':
		tomake['6'] += 1
	else:
		tomake[i] += 1
fro = defaultdict(lambda : 0)
for i in s:
	if i == '5':
		fro['2'] += 1
	elif i == '9':
		fro['6'] += 1
	else:
		fro[i] += 1
ans = math.inf
for i in tomake.keys():
	ans = min(ans, fro[i] // tomake[i])
print(ans)


t1 = map(int, input().strip())
t2 = map(int, input().strip())
ar1 = [0] * 10
ar2 = [0] * 10
for j in t1:
	ar1[j] += 1
for j in t2:
	ar2[j] += 1
ar1[2] += ar1[5]
ar1[6] += ar1[9]
ar1[5] = ar1[9] = 0
ar2[2] += ar2[5]
ar2[6] += ar2[9]
ar2[5] = ar2[9] = 0
print(int(min(map(lambda x: ar2[x] / ar1[x] if ar1[x] != 0 else 100500, range(10)))))


import traceback
import math
from collections import defaultdict, Counter
from functools import lru_cache
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def geti():
	return int(input())

def gets():
	return input()

def getil():
	return list(map(int, input().split()))

def getsl():
	return input().split()

def get2d(nrows, ncols, n=0):
	return [[n] * ncols for r in range(nrows)]
inf = float('inf')
mod = 10 ** 9 + 7

def main():
	z = lambda x: x.replace('2', '5').replace('6', '9')
	t = z(gets())
	s = z(gets())
	counts = Counter(s)
	reqs = Counter(t)
	return min((counts[k] // reqs[k] for k in reqs))
try:
	ans = main()
	print(ans)
except Exception as e:
	print(e)
	traceback.print_exc()


num = input()
str = input()
d = dict()
used = dict()
num = num.replace('5', '2')
str = str.replace('5', '2')
num = num.replace('9', '6')
str = str.replace('9', '6')
res = 10 ** 1000
for i in num:
	res = min(res, str.count(i) // num.count(i))
print(res)


(t, q, w, o) = (input(), {'0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0}, 0, 1)
for i in input():
	q[i] += 1
while o:
	for i in t:
		if i == '2':
			if q[i]:
				q[i] -= 1
			elif q['5']:
				q['5'] -= 1
			else:
				o = 0
		elif i == '5':
			if q[i]:
				q[i] -= 1
			elif q['2']:
				q['2'] -= 1
			else:
				o = 0
		elif i == '6':
			if q[i]:
				q[i] -= 1
			elif q['9']:
				q['9'] -= 1
			else:
				o = 0
		elif i == '9':
			if q[i]:
				q[i] -= 1
			elif q['6']:
				q['6'] -= 1
			else:
				o = 0
		elif q[i]:
			q[i] -= 1
		else:
			o = 0
	w += o
print(w)


import sys
t = int(sys.stdin.readline().strip())
cubes = [int(c) for c in list(sys.stdin.readline().strip())]

def flip(d):
	if d == 6:
		return 9
	elif d == 9:
		return 6
	elif d == 2:
		return 5
	elif d == 5:
		return 2

def build(t, cubes):
	for d in str(t):
		d = int(d)
		df = flip(d)
		if d in cubes:
			cubes.remove(d)
		elif df in cubes:
			cubes.remove(df)
		else:
			return (False, cubes)
	return (True, cubes)
i = 0
while True:
	(ok, cubes) = build(t, cubes)
	if ok:
		i += 1
	else:
		break
print(i)


from collections import defaultdict
ag = defaultdict(int)
for i in input():
	if i == '9':
		ag['6'] += 1
	elif i == '5':
		ag['2'] += 1
	else:
		ag[i] += 1
g = defaultdict(int)
for i in input():
	if i == '9':
		g['6'] += 1
	elif i == '5':
		g['2'] += 1
	else:
		g[i] += 1
ans = 999999999999999999
for i in ag:
	ans = min(ans, g[i] // ag[i])
print(ans)


def c(a, b):
	a = a.replace('6', '9')
	a = a.replace('2', '5')
	b = b.replace('6', '9')
	b = b.replace('2', '5')
	n = 10000
	for i in '01345789':
		t = a.count(i)
		if t != 0:
			n = min(n, b.count(i) // t)
	return n
a = input()
b = input()
print(c(a, b))


s1 = input()
s2 = input()
n = len(s1)
m = len(s2)
from collections import Counter
c1 = Counter(s1)
c2 = Counter(s2)
if c1['2'] and c1['5']:
	tot = c2['2'] + c2['5']
	a = c1['2']
	b = c1['5']
	c = a + b
	have2 = a / c * tot
	have5 = b / c * tot
elif c1['2'] or c1['5']:
	have2 = have5 = c2['2'] + c2['5']
if c1['6'] and c1['9']:
	tot = c2['6'] + c2['9']
	a = c1['6']
	b = c1['9']
	c = a + b
	have6 = a / c * tot
	have9 = b / c * tot
elif c1['6'] or c1['9']:
	have6 = have9 = c2['6'] + c2['9']
mini = 10 ** 9
for i in c1.keys():
	if i not in '2569' and c1[i]:
		mini = min(mini, c2[i] // c1[i])
if c1['2']:
	mini = min(mini, have2 // c1['2'])
if c1['5']:
	mini = min(mini, have5 // c1['5'])
if c1['6']:
	mini = min(mini, have6 // c1['6'])
if c1['9']:
	mini = min(mini, have9 // c1['9'])
mini = int(mini)
print(mini if mini != 10 ** 9 else 0)


def convert_string(string_list, len_string_list):
	change_dict = {}
	change_dict['9'] = '6'
	change_dict['5'] = '2'
	for i in range(len_string_list):
		if string_list[i] in change_dict:
			string_list[i] = change_dict[string_list[i]]

def form_frequency_dict(given_list):
	freq_dict = {}
	for i in given_list:
		if i in freq_dict:
			freq_dict[i] += 1
		else:
			freq_dict[i] = 1
	return freq_dict

def find_max_repititions(required_string_freq_dict, given_string_freq_dict):
	max_repititions = 201
	for (key, value) in required_string_freq_dict.items():
		if key in given_string_freq_dict:
			max_repititions_now_possible = given_string_freq_dict[key] // required_string_freq_dict[key]
			if max_repititions_now_possible < max_repititions:
				max_repititions = max_repititions_now_possible
	if max_repititions == 201:
		max_repititions = 0
	return max_repititions
import sys
inputlist = sys.stdin.readlines()
required_string = list(inputlist[0].strip())
given_string = list(inputlist[1].strip())
len_required_string = len(required_string)
len_given_string = len(given_string)
convert_string(required_string, len_required_string)
convert_string(given_string, len_given_string)
required_string_freq_dict = form_frequency_dict(required_string)
given_string_freq_dict = form_frequency_dict(given_string)
max_repititions = find_max_repititions(required_string_freq_dict, given_string_freq_dict)
print(max_repititions)


favornumb = {'0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '6': 0, '7': 0, '8': 0}
mass = {'0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '6': 0, '7': 0, '8': 0}
for i in input():
	if i == '2' or i == '5':
		favornumb['2'] += 1
	elif i == '6' or i == '9':
		favornumb['6'] += 1
	else:
		favornumb[i] += 1
for i in input():
	if i == '2' or i == '5':
		mass['2'] += 1
	elif i == '6' or i == '9':
		mass['6'] += 1
	else:
		mass[i] += 1
ans = 200
for i in ['0', '1', '2', '3', '4', '6', '7', '8']:
	if favornumb[i] == 0:
		continue
	else:
		pretend = int(mass[i] / favornumb[i])
		if pretend <= ans:
			ans = pretend
print(ans)


t = map(int, input().strip())
s = map(int, input().strip())
digits1 = [0] * 10
digits2 = [0] * 10
for i in t:
	digits1[i] += 1
digits1[2] += digits1[5]
digits1[6] += digits1[9]
digits1[5] = digits1[9] = 0
for i in s:
	digits2[i] += 1
digits2[2] += digits2[5]
digits2[6] += digits2[9]
digits2[5] = digits2[9] = 0
print(min(map(lambda x: digits2[x] // digits1[x] if digits1[x] != 0 else 999999, range(10))))


def re(s):
	t = ''
	for i in s:
		if i == '2' or i == '5':
			t += 'a'
		elif i == '6' or i == '9':
			t += 'b'
		else:
			t += i
	return t
from collections import defaultdict as dd

def main():
	t = re(input())
	s = re(input())
	req = dd(int)
	hv = dd(int)
	ans = 10 ** 9
	for i in t:
		req[i] += 1
	for j in s:
		hv[j] += 1
	for i in t:
		ans = min(ans, hv[i] // req[i])
	print(ans)
main()