def gcd(m, n)
    if m < n
        gcd(n, m)
    elsif n == 0
        [m, 0]
    else
        g, step = gcd(n, m % n)
        [g, step + 1]
    end
end

loop do
    x, y = gets.split.map &:to_i
    break if x == 0
    puts gcd(x, y) * ' '
end