use bigint;

my $max = 2370;

my @sieve = ();
my @primes = (1);
foreach my $n (2..$max) {
	if (not $sieve[$n]) {
		push @primes => $n;
		my $p = $#primes;
		my $m = $n;
		while ($m <= $max) {
			$sieve[$m] = $p;
			$m += $n;
		}
	}
}

sub a {
	my $n = shift;
	my @pow = ();
	while ($n>1) {
		my $p = $sieve[$n];
		my $prime = $primes[$p];
		while ($n % $prime==0) {
			$n /= $prime;
			$pow[$p]++;
		}
	}
	my $a = 1;
	my $xor = 0;
	foreach my $p (reverse 0..$#pow) {
		$xor ^= $pow[$p];
		$a *= $primes[$p] ** $xor;
	}
	return $a;
}

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