A truncatable prime is a prime number that when you successively remove digits from one end of the prime, you are left with a new prime number.



Examples

The number 997 is called a left-truncatable prime as the numbers 997, 97, and 7 are all prime.

The number 7393 is a right-truncatable prime as the numbers 7393, 739, 73, and 7 formed by removing digits from its right are also prime.

No zeroes are allowed in truncatable primes.



Task

The task is to find the largest left-truncatable and right-truncatable primes less than one million (base 10 is implied).



Related tasks
 
 Find largest left truncatable prime in a given base
 Sieve of Eratosthenes


See also

 Truncatable Prime from MathWorld.]


left(n)={
	my(v=[2,3,5,7],u,t=1,out=0);
	for(i=1,n,
		t*=10;
		u=[];
		for(j=1,#v,
			forstep(a=t,t*9,t,
				if(isprime(a+v[j]),u=concat(u,a+v[j]))
			)
		);
		out=v[#v];
		v=vecsort(u)
	);
	out
};
right(n)={
	my(v=[2,3,5,7],u,out=0);
	for(i=1,n,
		u=[];
		for(j=1,#v,
			forstep(a=1,9,[2,4],
				if(isprime(10*v[j]+a),u=concat(u,10*v[j]+a))
			)
		);
		out=v[#v];
		v=u
	);
	out
};
[left(6),right(6)]