# Enter your code here. Read input from STDIN. Print output to STDOUT
Sk_cache = dict()

def Sk(k):
    global Sk_cache
    if k in Sk_cache:
        return Sk_cache[k]
    res = 0
    if k <= 55:
        res = (100003 - 200003*k + 300007*(k**3)) % (10**6)
    else:
        res = (Sk(k-24) + Sk(k-55)) % (10**6)
    Sk_cache[k] = res
    return res

NUMBER, p = map(int, input().rstrip().split())

groups = 0
number2group = dict() # number -> a
group_cnt = dict() # a -> int
group_connection = set() # (a,b) 

number_found = False
target_number_group = 0
cur_p = 0

#print("NUMBER {} p {}".format(NUMBER, p))

i = 1
calls = 0
while (not number_found or cur_p < p*(10**4)) and i <= 2*10**6:
    calls += 1
    cur_number_from = Sk(2*calls-1)
    cur_number_to = Sk(2*calls)
    #print("call N{} from {} to {}".format(calls, cur_number_from, cur_number_to))
    if cur_number_from == NUMBER or cur_number_to == NUMBER:
        number_found = True
    
    number_from_group = 0
    number_to_group = 0
    if cur_number_from is number2group:
        #print("Already grouped 1")
        number_from_group = number2group[cur_number_from]
    if cur_number_to is number2group:
        #print("Already grouped 2")
        number_to_group = number2group[cur_number_to]
        
    #if number_from_group != number_to_group and number_from_group != 0 and number_to_group != 0:
    #    print("Connection found!")
        
    if number_from_group != number_to_group and number_from_group != 0 and number_to_group != 0 and (number_from_group, number_to_group) not in group_connection:
        group_connection.add((number_from_group, number_to_group))
        group_connection.add((number_to_group, number_from_group))
        prev_cnt = group_cnt[number_from_group]
        group_cnt[number_from_group] += group_cnt[number_to_group]
        group_cnt[number_to_group] += prev_cnt
        
    if number_from_group == 0 and number_to_group != 0:
        #print("Group extension 1")
        number_from_group = number_to_group
        number2group[cur_number_from] = number_to_group
        group_cnt[number_to_group] += 1
        
    if number_from_group != 0 and number_to_group == 0:
        #print("Group extension 2")
        number_to_group == number_from_group
        number2group[cur_number_to] = number_from_group
        group_cnt[number_from_group] += 1
    
    if number_from_group == 0 and number_to_group == 0 and cur_number_from != cur_number_to:
        groups += 1
        number2group[cur_number_to] = groups
        number2group[cur_number_from] = groups
        group_cnt[groups] = 2
        number_to_group = groups
        number_from_group = groups
        
    #if number_to_group != 0:
    #    if group_cnt[number_to_group] > 2:
    #        print("group {} number {}".format(number_to_group, group_cnt[number_to_group]))
    #if number_from_group != 0:
    #    if group_cnt[number_from_group] > 2:
    #        print("group {} number {}".format(number_from_group, group_cnt[number_from_group]))

    if cur_number_from == NUMBER or cur_number_to == NUMBER:
        number_found = True
        target_number_group = number2group[cur_number_from]
        source_number_group = number2group[cur_number_to]
        #print("call N{} from {} to {} groups {}, {} total_groups {}".format(calls, cur_number_from, cur_number_to, target_number_group, source_number_group, groups))
     
    if target_number_group != 0:
        cur_p = group_cnt[target_number_group]
        #print("{}".format(cur_p))
        
        
    i += 2
    
    
if number_found and cur_p >= p*(10**4):
    print("{}".format(calls))
    #print("target group count = {}".format(group_cnt[target_number_group]))
    #print("target group number = {}".format(target_number_group))
    #print("group connection {}".format(len(group_connection)))