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: import sys
def f(d,x,y):
    t = x % y
    x = y
    y = t
    if y != 0:
        return f(d+1,x,y)
    else:
        return (x,d+1)

while 1:
    y,x = sorted(list(map(int, input().split())))
    if x == 0: break
    ans = f(0,x,y)
    print(ans[0],ans[1])

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

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

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

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

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

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

Python: def gozyo(x,y):
    w = 0
    while True:
        if y == 0:
            return x,w
        x = x % y
        z = x
        x = y
        y = z
        w += 1
    

while True:
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        break
    if a < b:
        c = a
        a = b
        b = c
    u = gozyo(a,b)
    print(u[0],u[1])

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

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

Python: while True:

    x, y = [int(item) for item in input().split(" ")]

    if x == 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==0: break
    cnt = 0
    x,y = max(x,y),min(x,y)
    
    while y!=0:
        x,y = y,x%y; cnt += 1

    print(x,cnt)

Python: def gcd(a,b):
    i=0
    while b!=0:
        c=a%b
        a,b=b,c
        i+=1
    return [a,i]
            
while True:
    a,b=map(int,input().split())
    if a==0 and b==0:
        break
    if a<b:
        a,b=b,a
    print(*gcd(a,b))

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

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

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

    print(a, cnt)

Python: while True:
    x, y = [int(x) for x in input().split()]
    if x == 0 and y == 0:
        break
    
    c = 0
    if y > x:
        x,y = y, x
    while True:
        c += 1
        x = x % y
        x,y = y,x
        if y == 0:
            break
    
    print(x,c)

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

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: while True:
    a, b = map(int,input().split())
    X = 0
    Y = 0
    n = 0
    
    if a == 0 and b == 0:
        break

    if a >= b:
        X = a
        Y = b
    else:
        X = b
        Y = a

    while Y != 0:
        X,Y = Y,X%Y
        n += 1
    
    print(X,n)

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: for i in range(1000):
    x,y=map(int,input().split())
    if x==0 and y==0:
        break
    if y > x:
        x,y=y,x
    else:
        x,y=x,y


    count=0
    for i in range (1000):
        
        if y==0:
            break
        x=x%y
        x,y=y,x
        count+=1
        
        
    print("{} {}".format(x,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: while True:
    count=0
    a,b=map(int,input().split())
    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: #75 最大公約数-ユークリッドの互除法

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

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

    print(x, z)

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 1:
        count += 1
        z = x % y
        x, y = y, z
        if z == 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
    c = 0
    while True:
        if y == 0:
            break
        x = x % y
        x,y=y,x
        c += 1
    print(x,c)