$| = 1;

sub gcd {
	my ($u, $v) = @_;
	while ($v) {
		($u, $v) = ($v, $u % $v);
	}
	return abs($u);
}

my %seen = ();
my $min = 1;
my $N = 1;
my $rem = $N;
my $k = $min;
my $n = 0;

while ($n < 10_000) {
	while ($seen{$k} || gcd($N, $k)>1) {
		$k++;
	}
	$seen{$k}++;
	print ++$n, " ", $k, "\n";

	$rem--;
	if ($rem==0) {
		$rem = ++$N;
		while ($seen{$min}) {
			$min++;
		}
		$k = $min;
	}
}