# Appreciation

/*
 * Problem :: 2023 / 신기한 소수
 *
 * Kind :: Math + BFS
 *
 * Insight
 * - 에라토스테네스의 체를 사용할까 싶었는데...
 *   그러면 (int) P[10^8] 을 선언해야 하는데...
 *   스택에는 당연히 안들어가고 힙을 사용하는 전역배열로 선언했는데...
 *   시간 제한이 2초인데... 10^8 을 다 돌고 있으면...
 *   아마 시간 초과가 날 것 같다
 *   + 신기한소수
 *     왼쪽부터 각 자리까지 읽은 모든 숫자가 소수
 *     # 그럼 이렇게 생각할 수 있지 않을까?
 *       7 - 1자리 소수
 *       이를 바탕으로 파생되는 다음 2자리 소수 후보들
 *       71, 73, 77, 79
 *       (일의자리가 0, 2, 4, 5, 6, 8 은 2또는 5의 배수라 소수일 수 없음)
 *       -> 이제 71, 73, 77, 79 가 소수인지 검사하고
 *          소수임이 밝혀진 수들을 통해서 또 다음자리의 신기한 소수를 알아내면 된다!
 *          => Queue 를 이용해서 현재 몇 자리수의 신기한 소수를 찾는지 다루어 주자
 *             현재 Queue 에 들어있는 신기한 소수들의 개수만큼
 *             que.front(), que.pop() 을 통해 순회하면서
 *             각각의 신기한 소수마다 다음자리의 신기한 소수들을 찾아주자
 *             이 경우, 10^8 이나 되는 수들이 모두 소수인지 검사하지 않으므로
 *             시간 제한내에 충분히 풀 수 있겠지? <= 그랬다고 합니다
 *
 * Point
 * - que 에 1의 자리 신기한 소수를 넣은 순서도 오름차순 (초기화),
 *   다음자리 신기한 소수를 찾는 순서도 오름차순이기 때문에
 *   따로 que 안의 원소들을 정렬하지 않아도 오름차순으로 이미 정렬된 상태이다
 *   따라서, 추가적인 정렬없이 그냥 출력해주면 된다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <queue>

using namespace std;

#define endl '\n'

// Set up : Global Variables


// Set up : Functions Declaration
bool isPrime(int n);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;

    // Process
    queue<int> que;

    int cnt = 1; /* 현재 que 에 들어있는 신기한 소수들의 자리수 */
    /* 1자리 수의 신기한 소수들 */
    que.push(2);
    que.push(3);
    que.push(5);
    que.push(7);

    int D[4] = {1, 3, 7, 9}; /* 다음자리의 신기한 소수 후보들에 가능한 일의 자리 숫자 */
    while (cnt++ < N) { /* 현재 신기한 소수들의 자리수가 N 보다 작다면 */
        int size = que.size(); /* 현재 que 에 들어있는 신기한 소수들의 개수 */
        while (size--) { /* size 만큼 신기한 소수들 순회 */
            int c = que.front(); que.pop();
            for (int d : D) {
                int n = 10*c + d; /* 현재 신기한 소수에서 파생되는
                                   * 다음 자리 신기한 소수 후보 */
                if (isPrime(n)) { /* 후보가 소수라면 */
                    que.push(n); /* que 에 추가 */
                }
            }
        }
    }

    // Control : Output
    /* que 에 들어있는 신기한 소수를 모두 출력
     * 초기화 및 다음자리 후보들 찾을 때 모두 오름차순으로 과정이 이루어졌기 때문에
     * que 는 이미 오름차순으로 정렬된 상태 */
    while (not(que.empty())) {
        cout << que.front() << endl;
        que.pop();
    }
}

// Helper Functions
bool isPrime(int n)
/* n 이 소수면 true 를 반환, 그 외 false 를 반환 */
{
    if (n == 0 || n == 1) return false;
    for (int i=2; i*i<=n; i++) {
        if (n%i == 0) return false;
    } return true;
}