$| = 1;

my $max = 1000;

my @properDivisor = ();
foreach my $n (1..$max) {
	my $m = 2*$n;
	while ($m<=$max) {
		push @{$properDivisor[$m]} => $n;
		$m += $n;
	}
}

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

my @a = ();
my %yetInTheSequence = ();

my $min = 1;
sub a {
	my $n = shift;
	foreach my $a ($min..$max) {
		if (not $yetInTheSequence{$a}) {
			my $coprime = 1;
			foreach my $d (@{$properDivisor[$n]}) {
				if (gcd($a[$d],$a)>1) {
					$coprime = 0;
					last;
				}
			}
			if ($coprime) {
				$a[$n] = $a;
				$yetInTheSequence{$a}++;
				while ($yetInTheSequence{$min}) {
					$min++;
				}
				return $a;
			}
		}
	}
	exit;
}

foreach my $n (1..$max) {
	$a[$n] = a($n);
	print "$n $a[$n]\n";
}