$| = 1;

use bigint;

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

my %known = (1=>1);
my %seen = (1=>1);

sub a {
	my $n = shift;

	if (not exists $known{$n}) {
		my $a = 1;
		while (1) {
			if (not exists $seen{$a}) {
				my %newseen = %seen;
				my %newknown = %known;
				my $good = 1;

				foreach my $p (keys %known) {
					if (gcd($n, $p)==1) {
						my $z = $a * $known{$p};
						if ($z==$n*$p) {
							$good = 0;
							last;
						}

						if (not exists $newseen{$z}) {
							$newseen{$z} = 1;
							$newknown{$n * $p} = $z;
						} else {
							$good = 0;
							last;
						}
					}
				}

				if ($good) {
					%seen = %newseen;
					%known = %newknown;
					last;
				}
			}
			$a++;
		}
	}

	return $known{$n};
}

foreach my $n (1..10_000) {
	print $n, " ", a($n), "\n";

}