Baekjoon-2023-신기한 소수

import sys
import math
input = sys.stdin.readline

N = int(input())

# Get all prime numbers in range(2, sqrt(10^N))
prime_n = [2]
for i in range(3, int(math.sqrt(10**N))):
    isprime = 1
    for p in prime_n:
        if i % p == 0:
            isprime = 0
            break
    if isprime:
        prime_n.append(i)

amaz_prime_n = [[] for _ in range(8)]
amaz_prime_n[0] = [2,3,5,7]
for n in range(1,N):
    for a_p in amaz_prime_n[n-1]:
        for j in range(10):
            new_n = 10*a_p + j
            isprime = 1
            for p in prime_n:
                if new_n % p == 0:
                    isprime = 0
                    break
                if p > math.sqrt(new_n):
                    break
            if isprime:
                amaz_prime_n[n].append(new_n)

print(*amaz_prime_n[N-1],sep='\n')