Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() (int, error) {
	return strconv.Atoi(nextString())
}

func gcd(x, y int) (int, int) {
	nSteps := 0
	for {
		if x < y {
			tmp := x
			x = y
			y = tmp
		}
		nSteps++
		if x%y == 0 {
			return nSteps, y
		}
		x = x % y
	}
}

func main() {
	scanner.Split(bufio.ScanWords)

	for {
		a, _ := nextInt()
		b, _ := nextInt()

		if a == 0 && b == 0 {
			break
		}

		nSteps, p := gcd(a, b)
		fmt.Println(p, nSteps)
	}
}

Python: while True:
    l = []
#    x , y = reversed(list(map(int, input().split())))
    x , y = map(int, input().split())
    if (x,y) == (0,0):
        break
    #print(x,y,"*")

    if x<=y :
        def gcd(y, x):
            if x == 0:
                #print(l,x,y,"$")
                return y
            else:
                l.append(1)
                #print(l,x,y)
                return gcd(x, y % x) #再帰
        print(gcd(y,x),end="")
        print("",sum(l))
    elif x == y :
        print(x,1)

    else:
        def gcd(x, y):
            if y == 0:
                #print(l,x,y,"*")
                return x

            else:
                l.append(1)
                #print(l,x,y)
                return gcd(y, x % y) #再帰

        print(gcd(x,y),end="")
        print("",sum(l))

Python: while True:
    n,m = map(int,input().split())
    if n==0 and m==0:
        break
    step = 0
    if n >= m:
        X = n
        Y = m
        while True:
            X = X % Y
            X,Y = Y,X
            step +=1
            if Y == 0:
                ans = X
                break
    else:
        X = m
        Y = n
        while True:
            X = X % Y
            X,Y = Y,X
            step +=1
            if Y == 0 :
                ans = X
                break
    print(ans,step)

Python: while True:
    a, b = map(int,input().split())
    if a==0 and b==0:
        break
    if a <= b:
        a, b = b, a
    d = 1
    while True:
        c = a%b
        if c==0:
            break
        if c!=0:
            a,b = b, c
            d += 1
    print(b,d)

Python: while True:
    a, b = map(int, input().split())
    if a == b == 0: break
    if a < b:
        a, b = b, a
    c = 0
    while b > 0:
        a, b, c = b, a%b, c+1
    print(a, c)

Python: while True:
    x,y=map(int,input().split())
    if x==0 and y==0:
        break
    num=0
    while True:
        num+=1
        if x==0:
            print(y,num-1)
            break
        elif y==0:
            print(x,num-1)
            break
        
        elif x>=y:
            x=x%y
        elif x<y:
            y=y%x

Python: while True:
    n,m=map(int,input().split())
    if n==0 and m==0:
        break
    
    X=max(n,m)
    Y=min(n,m)
    
    a=0
    while True:
        a+=1
        tmp=X%Y
        X,Y=Y,tmp
        if tmp==0:
            break
        
    print(X,a)

Python: def euclidean_algorithm(x, y):
    cnt = 0

    if x < y:
        x, y = y, x
    while y:
        x = x % y
        x, y = y, x
        cnt += 1
    return x, cnt

import sys
f = sys.stdin

while True:
    a, b = map(int, f.readline().split())
    if a == 0:
        break
    print(*euclidean_algorithm(a, b))

Python: while True :
    a, b = map(int, input().split())

    if a == 0 :
        break
    else :
        if a <= b :
                X, Y = b, a
        else :
            X, Y = a, b
            
        cnt = 0
                
        def Euc(X, Y, cnt) :
            while Y != 0 :
                cnt += 1
                X %= Y
                X, Y = Y, X
                
            return X, cnt
            
        print(Euc(X, Y, cnt)[0], Euc(X, Y, cnt)[1])

Python: while True:
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        break
    X = max(a,b)
    Y = min(a,b)
    
    count = 0
    while True:
        count += 1
        d = X % Y
        X,Y = Y,d
        if d == 0:
            break
    print(X,count)

Python: while True:
    x, y = map(int, input().split())
    
    if x==0 and y==0:
        break
    
    if x<y:
        x, y = y, x
    
    count = 0
    while y>0:
        x = x%y
        x, y = y, x
        count += 1
    
    print(x,count)

Python: while True:
    x,y=map(int,input().split())
    if x<=y:
        x,y=y,x
    if x==y==0:
        break
    z=0
    while True:
        if y==0:
            break
        x=x%y
        x,y=y,x
        z+=1
    print(x,z)

Python: while True:
    m,n=map(int,input().split())
    if m==n==0:
        break
    b=0
    if m<n:
        m,n=n,m
    while n!=0:    
        a=m%n
        m=n
        n=a
        b+=1
    print(m,b)

Python: while True:
    c=0
    n,m=map(int,input().split())
    if n==0 and m==0:
        break
    if n<m:
        n,m=m,n
    while True:
        if m==0:
            print(n,c)
            break
        n=n%m
        n,m=m,n
        c=c+1

Python: while True:
    a,b=map(int,input().split())
    if a==0 and b==0:
        break
    c=0
    if a<b:
        a,b=b,a
    while b!=0:
        c+=1
        d=a%b
        a=b
        b=d
    print(a,c)

Python: # -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0197

"""
import sys
from sys import stdin
input = stdin.readline


def solve(a, b):
    count = 0
    if a > b:
        X, Y = a, b
    else:
        X, Y = b, a

    r  = 1
    while r:
        r = X % Y
        X = r
        X, Y = Y, X
        count += 1
    return X, count


def main(args):
    while True:
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            break
        gcd, count = solve(a, b)
        print(gcd, count)


if __name__ == '__main__':
    main(sys.argv[1:])

Python: while True:
    a,b = map(int,input().split())
    count = 0
    if a == 0 and b == 0:
        break
    elif a < b:
        a,b = b,a
        
    while True:
        if b == 0:
            break
        a = a % b
        a,b = b,a
        count += 1
    print(a,count)

Python: while True:
    try:
        a,b=map(int,input().split())
        if a==0 and b==0:
            break
        else:
            if a<b:
                a,b=b,a
            else:
                pass
            i=0
            while True:
                c=a%b
                a=b
                b=c
                i+=1
                if b==0:
                    break
            print(a,i)
    except EOFError:
        pass

Python: def gcd(a, b):
	k = 0
	while b != 0:
		r = a % b
		a, b = b, r
		k += 1
	return [a, k]

while True:
	x, y = list(map(int, input().split()))
	if x == 0: break
	if x < y: x, y = y, x
	ans = gcd(x, y)
	print(*ans)

Python: while True:
    a,b = [int(i) for i in input().split()]

    if a == 0 and b == 0:
        break

    if a < b:
        a,b = b,a

    c = 0
    while b > 0:
        a, b = b, a % b
        c += 1

    print(a, c)

Python: # Aizu Problem 0197: Greatest Common Divisor: Euclidean Algorithm
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def extended_gcd(a, b):
    steps = 0
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = b, a
    while r != 0:
        steps += 1
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
        old_t, t = t, old_t - q * t
    return old_r, steps


while True:
    a, b = [int(_) for _ in input().split()]
    if a == b == 0:
        break
    g, steps = extended_gcd(a, b)
    print(g, steps)

Python: 
import datetime

while 1:
    c = 0
    a,b = map(int,input().split())
    if a == 0:
        break

    if b > a:
        a,b = b,a

    while b != 0:
        a = a % b
        a, b = b, a
        c += 1
    print(a,c)