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: interview

Starter code:

Solutions:
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)))))

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)


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


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)


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)

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())

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)

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)



# Made By Mostafa_Khaled


t = map(int, input().strip())
s = map(int, input().strip())

digits1 = [0] * 10 # makes a list of size 10 filled with zeros.
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))))

# init
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]))



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)


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 )

# import numpy as np

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()
# input-output by console


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)

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)


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 list(tomake.keys()):
    ans=min(ans,fro[i]//tomake[i])
print(ans)


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
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)

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)


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]]
    #print(string_list)
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())
#print(required_string,given_string)
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)
#print(required_string,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)

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()