#!/usr/bin/env python3

def primes(x,y):
    #pra stevila do xa
    nums=[True]*x
    primes=[2]
    i=3
    roots={}
    dig=1
    poss=[]
    while i<x:
        if i>=10**dig:
            if poss:
                poss=[n for n in poss if len(n)==y]
                if poss:
                    return min(map(min, poss))
            dig+=1
            roots={}
        if nums[i-1]==True:
            n=str(i)
            roll=[]
            for r in set(n):
                j=0
                while n[j]!=r:
                    j+=1
                roll.extend(dig_replacement([n[:j]+"*",n[:j+1]],n[j+1:],r))
            for j in roll:
                l=roots.setdefault(j,[])
                l.append(i)
                if len(l)==y:
                    poss.append(l)
            primes.append(i)
            j=i*2
            while j<x:
                nums[j-1]=False
                j+=i
        i+=2
    return False

def dig_replacement(starts,end,num):
    i=0
    while i<len(end):
        if end[i]==num:
            return dig_replacement([j+end[:i]+"*" for j in starts]+[j+end[:i+1] for j in starts],end[i+1:],num)
        i+=1
    return [j+end for j in starts][:-1]

if __name__ == '__main__':
    print(primes(2 * 10**6, 8))