$| = 1;

sub overlaps {
	my $a = shift;
	my $b = shift;

	if (index($a, $b)>=0 || index($b, $a)>=0) {
		return 1;
	}

	my $la = length($a);
	my $lb = length($b);

	my $l = ($la < $lb) ? $la : $lb;

	foreach (1..$l) {
		if (substr($a, 0, $_) eq substr($b, $lb-$_)) {
			return 1;
		}
		if (substr($b, 0, $_) eq substr($a, $la-$_)) {
			return 1;
		}
	}

	return 0;
}

my $max = 1_000_000;
my @sieve = ();
my @primes = ();

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

my %seen = ();

sub other {
	my $prev = shift;
	$seen{$prev} = 1;
	while ($seen{$primes[0]}) {
		shift @primes;
	}

	foreach my $prime (@primes) {
		if ((not exists $seen{$prime}) and overlaps($prev, $prime)) {
			return $prime;
		}
	}

	die;
}

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