#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define WANTED 10000
#define MAX (WANTED*WANTED+1)

bool seen[MAX];

int prevm = 0;
int minm = 0;

int other(int m) {
	if (prevm!=m) {
		prevm = m;
		minm = m;
	}

	for (int v=minm; v<MAX; v+=m) {
		if (!seen[v]) {
			seen[v] = true;
			while (minm < MAX && seen[minm]) {
				minm += m;
			}
			return v;
		}
	}

	return WANTED+1;
}

int main() {
	memset(seen, 0, sizeof(seen));

	int rem = WANTED;

	int wanted[1+WANTED];
	memset(wanted, 0, sizeof(wanted));

	for (int sqrtint=1; rem; sqrtint++) {
		for (int n=sqrtint*sqrtint; n<(sqrtint+1)*(sqrtint+1); n++) {
			int v = other(sqrtint);
			if (v<=WANTED) {
				rem--;
				wanted[v] = n;
			} else {
				break;
			}
		}
	}

	for (int w=1; w<=WANTED; w++) {
		printf("%d %d\n", w, wanted[w]);
	}

	return 0;
}