//bouzian najib
//le 11/12/2009
#include<stdlib.h>
#include<stdio.h>
typedef unsigned long long ullong;
int iter(ullong a, ullong b)
{
    ullong r;
    int cpt = 0;
    while (b > 0) {
	r = a % b;
	a = b;
	b = r;
	cpt = cpt + 1;
    }
    return cpt;
}

int main(int argc, char *argv[])
{
    ullong a, b;
    int n, max;
    n = atoi(argv[1]);
    for (b = 0; b < n; b++) {
	max = 0;
	for (a = 0; a < b; a++)
	    if (iter(a, b) > max)
		max = iter(a, b);
	printf("%Ld  %d\n", b, max);
    }
    return 0;
}