Go: package main

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

var scanner = bufio.NewScanner(os.Stdin)

func main() {
	for scanner.Scan() {
		buf := strings.Split(scanner.Text(), " ")
		a, _ := strconv.Atoi(buf[0])
		b, _ := strconv.Atoi(buf[1])
		if a == 0 && b == 0 {
			break
		}
		if a < b {
			a, b = b, a
		}
		cnt := 0
		for b != 0 {
			a = a%b
			a, b = b, a
			cnt++
		}
		fmt.Println(a, cnt)
	}
}

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):
    if a < b:
        a, b = b, a
    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: # coding: utf-8
# Your code here!

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

Python: def solve():
    from sys import stdin
    f_i = stdin
    
    ans = ""
    
    while True:
        a, b = map(int, f_i.readline().split())
        
        if a == 0 and b == 0:
            break
        
        if a < b:
            a, b = b, a
        
        # Euclidean Algorithm
        cnt = 1
        while a % b != 0:
            cnt += 1
            a, b = b, a % b
        
        ans += f"{b} {cnt}\n"
    
    print(ans, end='')

solve()

Python: def gcd(a,b):
    c = 0
    while b != 0:
        a,b = b,a % b
        c += 1
    return [a,c]
    
while 1:
    x,y = map(int,input().split())
    if x == 0:
        break
    
    x,y = max(x,y),min(x,y)
    print(*(gcd(x,y)))

Python: # AOJ 0197 Greatest Common Divisor
# Python3 2018.6.18 bal4u

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: def gcd(a,b):
    c = 0
    while b:
        (a,b),c = (b,a%b),c+1
    print(a,c)
        
while True:
    N,M = map(int,input().split())
    if N == 0:
        break
    gcd(N,M) if N>M else gcd(M,N)

Python: def gcd(a,b):
    k=0
    while b != 0:
        r=a%b
        a=r
        a,b=b,a
        k+=1
    return[a,k]
        
while True:
    m,n=map(int,input().split())
    if m==0:break
    if m<n:m,n=n,m
    ans = gcd(m, n) #print(math.gcd(a, b)) #二つの整数を渡すと最大公約数を返す    s=0
    print(*ans)

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

Python: # coding: utf-8
# 75
k=0

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

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
            
        s=0
                
        def c(X, Y, s) :
            while Y != 0 :
                s += 1
                X %= Y
                X, Y = Y, X
                
            return X, s
            
        print(c(X, Y, s)[0], c(X, Y, s)[1])

Python: while True:
    a,b=map(int,input().split())
    if a==b==0:
        break
    else:
        if a>=b:
            x=a
            y=b
        else:
            x=b
            y=a
        
        s=0
        while True:
            x=x%y
            x,y=y,x
            
            s+=1
            if y==0:
                break
        print(x,s)

Python: # coding: utf-8
# Your code here!

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

Python: while True:
    a,b=map(int,input().split())
    if a==0 and b==0:
        break
    if a>=b:
        X=a
        Y=b
    else:
        X=b
        Y=a
    C=0    
    while Y!=0:
        X=X%Y  
        X,Y=Y,X
        C+=1
    else:
        print(X,C)

Python: while True:
    try:
        m = list(map(int,input().split()))
        if m[0] == 0 and m[1] == 0:
            break
    except EOFError:
        break

    m.sort(reverse=True)
    x = m[0]
    y = m[1]
    a = 0
    while y != 0:
        a += 1
        x = x % y
        x,y = y,x

    print(x,a)

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

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

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

    x = max(a, b)
    y = min(a, b)

    cnt = 0
    while 1:
        cnt += 1
        tmp = x % y
        x, y = y, tmp
        if tmp == 0:
            break

    print(x, cnt)

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

    while y > 0:
        x, y = y, x%y
        count += 1
    print(x, count)

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

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
    if a < b:
        a, b = b, a
    C = 0
    while True:
        C  = C + 1
        a = a % b
        if a == 0:
            break
        a, b = b, a
    print(b, C)

Python: # 75
while True:
    X,Y = (int(x) for x in input().split())
    if X == 0 and Y == 0:
        break
    elif X < Y:
        X,Y = Y,X

    i = 0
    while Y != 0:
        X = X % Y
        X,Y = Y,X
        i += 1

    print(X, i)

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

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

Python: def Euclidean(a,b):
    if a>=b:
        x=a
        y=b
    else:
        x=b
        y=a
    n=0
    while y!=0:
        x=x%y
        x,y=y,x
        n+=1
    print(x,n)

while True:
    a,b=map(int,input().split())
    if a==0 and b==0:
        break
    Euclidean(a,b)

Python: def gcd(a,b):
    c=0
    while b:(a,b),c=(b,a%b),c+1
    print(a,c)
while 1:
    n,m=map(int,input().split())
    if n==0:break
    gcd(n,m)