import java.math.BigInteger;
import java.util.Scanner;

/**
 * Calculates the greatest common divisor of two integers recursively
 * and prints the number of function calls required to calculate them
 */
public class Solution
{
	/**
	 * Gets data from standard input
	 */
	private Scanner input = null;

	/**
	 * Number of function calls requierd to calculate the gcd
	 */
	private long callCount = 0;

	/**
	 * Start the execution of the solution
	 * @param args Command line arguments
	 */
	public static void main(String args[])
	{
		Solution solution = new Solution();
		solution.run();
	}

	/**
	 * Run the solution. This method is called from main()
	 */
	public void run()
	{
		// Create object to read data from standard input
		this.input = new Scanner(System.in);

		// Mientras hayan parejas de numeros
		while ( this.input.hasNextBigInteger() )
		{
            BigInteger numero1 = this.input.nextBigInteger();
            BigInteger numero2 = this.input.nextBigInteger();
            this.callCount = 0;
            BigInteger mcd = maximoComunDivisor( numero1.abs(), numero2.abs() );
            
			System.out.printf("%,d %,d: %,d (%d)%n", numero1, numero2, mcd, this.callCount);
		}

		// Close the standard input
		this.input.close();
	}

    public BigInteger maximoComunDivisor(BigInteger a, BigInteger b)
    {
        ++this.callCount;
        
        if ( b.equals( BigInteger.ZERO ) )
        {
            return a;
        }
        else
        {
            return maximoComunDivisor( b, a.remainder(b) );
        }
    }
    
    public long maximoComunDivisor(long a, long b)
    {
        ++this.callCount;
        
        if ( b == 0 )
        {
            return a;
        }
        else
        {
            return maximoComunDivisor(b, a % b);
        }
    }
}