def lineal(a,d)
  #p "lineal: #{a},#{d}"
  q=[[a,0]]
  until q.empty?
    #p q
    node,dist=q.shift
    dist+=1
    i=1
    loop{
      break if (i+=1)**2>node
      next if 0!=node%i
      [i,node/i].each{|j|
        t=j+1
        return dist if t==d
        q.push([t,dist]) if t>d
      }
    }
  end
  nil
end
def maketree(root,min)
  just=[]
  #p min
  t=(f=->current,parent{
    #p "f: #{current}"
    ret=[current,parent,children=[]]
    just.push(ret) if current==min
    return ret if current<=min
    i=1
    loop {
      break if (i+=1)**2>current
      next if 0!=current%i
      children.push(f[current/i+1,ret])
      children.push(f[i+1,ret]) if i+1>=min
    }
    ret
  })[root,nil]
  just
end
def solve(input)
  root,*c=input.split(/\D/).map(&:to_i)
  small,big=c.sort
  min=lineal(big,small)
  return min if min==1||big==root
  just=maketree(root,big)
  just.each{|leaf|
    node,i=leaf,0
    while node=node[1]
      i+=1
      dist=lineal(node[0],small) or next
      min=i+dist if !min||min>i+dist
    end
  }
  min
end
 
def test(n,input,expected)
  actual=solve(input).to_s
  puts "#{n}: "+(actual==expected ? "ok":"ng ( #{actual} against #{expected} for #{input} )")
end
 
test( 0, "50:6,3", "1" )
test( 1, "98:5,11", "4" )
test( 2, "1000:33,20", "7" )
test( 3, "514:9,18", "8" )
test( 4, "961:5,4", "3" )
test( 5, "1369:1369,3", "2" )
test( 6, "258:16,12", "5" )
test( 7, "235:13,3", "2" )
test( 8, "1096:19,17", "8" )
test( 9, "847:7,17", "6" )
test( 10, "1932:3,5", "2" )
test( 11, "2491:4,8", "3" )
test( 12, "840:421,36", "2" )
test( 13, "1430:37,111", "3" )
test( 14, "496:17,9", "2" )
test( 15, "891:6,10", "1" )
test( 16, "1560:196,21", "2" )
test( 17, "516:20,12", "5" )
test( 18, "696:30,59", "2" )
test( 19, "1760:5,441", "2" )
test( 20, "1736:11,26", "5" )
test( 21, "1518:17,34", "4" )
test( 22, "806:63,16", "5" )
test( 23, "1920:3,97", "2" )
test( 24, "1150:13,22", "4" )
test( 25, "920:116,5", "1" )
test( 26, "2016:7,337", "2" )
test( 27, "408:9,25", "2" )
test( 28, "735:36,8", "2" )
test( 29, "470:5,31", "2" )
test( 30, "2100:12,351", "3" )
test( 31, "870:36,10", "1" )
test( 32, "1512:253,13", "2" )
test( 33, "697:12,15", "3" )
test( 34, "1224:5,14", "2" )
test( 35, "986:125,17", "3" )
test( 36, "864:12,13", "3" )
test( 37, "500:21,51", "2" )
test( 38, "819:33,21", "4" )
test( 39, "594:55,3", "2" )
test( 40, "638:17,24", "3" )