#include<iostream>
#include<map>
using namespace std;
int gcd(int x, int y);
int euc(int x, int y, int f);
int main(){
  int n,m;
  while(cin >>n>>m,n||m){
    if(n<m){int c = n; n = m; m = c;}
    cout <<gcd(n,m)<<" "<<euc(n,m,0)<<endl;
  }
  return 0;
}
int gcd(int x, int y){
  if(y == 0){return x;}
  return gcd(y,x%y);
}
int euc(int x, int y, int f){
  if(y == 0){return f;}
  f++;
  return euc(y,x%y,f);
}