use strict;
use prime;
use Math::BigInt;

my $max = 0;
my $d = 0;

for (my $i = 1; $i < 1000; ++$i) {
	if (is_rotate($i)) {
		print $i,"\n";
		my $j = 0;
		for ($j = 1; ; ++$j) {
			my $b = new Math::BigInt(10);
			$b->bpow($j);
			$b->bmod($i);
			if (!$b->bcmp(1)) {
				if ($j > $max) {
					$max = $j;
					$d = $i;
				}
				last;
			}
		}
	}
}
print "$d:$max\n";

sub is_rotate
{
	my $n = shift;
	my @prime = prime::get_prime_divisor($n);
	my $f2 = 0;
	my $f5 = 0;
	if ($n == 1) {
		return 0;
	}
	foreach my $p (@prime) {
		if ($p == 2) {
			$f2 = 1;
		} elsif ($p == 5) {
			$f5 = 1;
		}
	}
	
	return (!$f2 && !$f5);
}