#include <bits/stdc++.h>

using namespace std;

int main(){

  int X,Y,c=0;
  vector<int> x,C;
  while(true){
    cin>>X>>Y;
    if(X+Y==0) break;
    c=0;
    while(true){
      X %= Y;
      swap(X,Y);
      ++c;
      //cout << "/////////  "<< X<<" "<<Y<<" "<< c << endl;
      if(Y==0){
	//cout << X << " " << c << endl;
	x.push_back(X);
	C.push_back(c);
	break;
      }
    }
  }

  for(int i=0; i<x.size(); ++i){
    cout<<x[i]<<" "<<C[i]<<endl;
  }

  
  return 0;
}

