#include <bits/stdc++.h>
using namespace std;

bool prime[8000];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("BEAUTY3.INP", "r", stdin);
    freopen("BEAUTY3.OUT", "w", stdout);

    // Sàng Eratosthenes để tìm số nguyên tố
    // Giới hạn 8000 vì số lớn nhất của tổng lập phương 10 chữ số (10*9^3 = 7290)
    for (int i = 2; i < 8000; i++) prime[i] = true;
    for (int i = 2; i * i < 8000; i++)
        if (prime[i])
            for (int j = i * i; j < 8000; j += i)
                prime[j] = false;

    vector<int> beauty;
    // Tạo mảng chứa các số đẹp
    // Với N tối đa 1,000,000, ta cần khoảng 10,000,000 số đầu tiên để đủ số đẹp
    beauty.reserve(8000000);

    for (int x = 1; x <= 80000000; x++) {
        int t = x, s = 0;
        while (t) {
            int d = t % 10;
            s += d * d * d;
            t /= 10;
        }
        if (prime[s]) beauty.push_back(x);
    }

    int T;
    cin >> T;
    while (T--) {
        long long N;
        cin >> N;
        cout << beauty[N - 1] << "\n";
    }
}

#include <bits/stdc++.h>
using namespace std;

const int MAX_SIEVE = 8000;
vector<bool> is_prime(MAX_SIEVE, true);
vector<int> beautiful;

void sieve() {
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < MAX_SIEVE; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAX_SIEVE; j += i)
                is_prime[j] = false;
        }
    }
}

int sum_cubes(int n) {
    int s = 0;
    while (n > 0) {
        int d = n % 10;
        s += d * d * d;
        n /= 10;
    }
    return s;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    freopen("BEAUTY3.INP", "r", stdin);
    freopen("BEAUTY3.OUT", "w", stdout);

    sieve();

    // Tính toán số đẹp
    // Dựa trên quan sát, mật độ số đẹp khá cao.
    // Để có 10^6 số đẹp, cần duyệt khoảng 10^7 số.
    // Ta dùng mảng động để tiết kiệm vùng nhớ stack.
    int limit = 15000000; 
    beautiful.reserve(limit);

    for (int x = 1; beautiful.size() < 1000000; x++) {
        if (is_prime[sum_cubes(x)]) {
            beautiful.push_back(x);
        }
    }

    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        cout << beautiful[n-1] << "\n";
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <cmath>
#include <fstream>
#include <algorithm>

using namespace std;

const int SIEVE_LIMIT = 8000;
const int MAX_BEAUTIFUL = 1000000;

vector<bool> is_p(SIEVE_LIMIT + 1, true);
vector<int> beautiful_numbers;

void sieve() {
    is_p[0] = is_p[1] = false;
    for (int p = 2; p * p <= SIEVE_LIMIT; p++) {
        if (is_p[p]) {
            for (int i = p * p; i <= SIEVE_LIMIT; i += p)
                is_p[i] = false;
        }
    }
}

int sum_of_cubes(long long n) {
    int sum = 0;
    string s = to_string(n);
    for (char c : s) {
        int digit = c - '0';
        sum += digit * digit * digit;
    }
    return sum;
}

void generate_beautiful_numbers() {
    long long current_num = 1;
    while (beautiful_numbers.size() < MAX_BEAUTIFUL) {
        int sum_cub = sum_of_cubes(current_num);
        if (sum_cub < SIEVE_LIMIT && is_p[sum_cub]) {
            beautiful_numbers.push_back(current_num);
        }
        current_num++;
    }
}

int main() {
    sieve();
    generate_beautiful_numbers();

    ifstream in("BEAUTY3.INP");
    ofstream out("BEAUTY3.OUT");

    int T;
    in >> T;
    while (T--) {
        long long N;
        in >> N;
        out << beautiful_numbers[N - 1] << "\n";
    }
    return 0;
}