#include <stdio.h>

int ints_get (int *a)
{
  int result = 0;
  while (scanf ("%d", &a[result]) != EOF)
    result++;
  return result;
}

void metal (int *metais, int n_metais)
{
	int i, comp, larg, x;
	int out[64];
	int n_out = 64;
	for (i = 0; i < n_out; i++)
		out[i] = 0;
	for (i = 0; i < n_metais; i+=2)
	{
		comp = metais[i];
		larg = metais[i+1];
		while ( comp > 0 && larg > 0)
		{
			out[larg] += comp / larg;
			x = larg;
			larg = comp % larg;
			comp = x;
		}
	}
	for (i = n_out -  1; i >= 0; i--)
	{
		if (out[i] != 0)
		{
			printf ("%d", i);
			printf (" ");
			printf ("%d\n", out[i]);
		}
	}
}

void teste_metal (void);

int main (void)
{
	teste_metal();
	return 0;
}

void teste_metal (void)
{
	int metais[64];
	int n_metais;
	n_metais = ints_get(metais);
	metal (metais, n_metais);
}