public class Euler845 {
    static final int kMaxLen = 20;
    static final int kMaxSum = 9 * kMaxLen;

    static class DigitPrimeDP {
        boolean[] isPrime;
        long[][] ways;
        long[][] good;

        DigitPrimeDP() {
            isPrime = new boolean[kMaxSum + 1];
            ways = new long[kMaxLen + 1][kMaxSum + 1];
            good = new long[kMaxLen + 1][kMaxSum + 1];

            sievePrimes();
            buildWays();
            buildGood();
        }

        void sievePrimes() {
            java.util.Arrays.fill(isPrime, true);
            isPrime[0] = false;
            isPrime[1] = false;
            for (int p = 2; p * p <= kMaxSum; ++p) {
                if (!isPrime[p])
                    continue;
                for (int x = p * p; x <= kMaxSum; x += p)
                    isPrime[x] = false;
            }
        }

        void buildWays() {
            ways[0][0] = 1;
            for (int len = 1; len <= kMaxLen; ++len) {
                for (int s = 0; s <= 9 * (len - 1); ++s) {
                    long cur = ways[len - 1][s];
                    if (cur == 0)
                        continue;
                    for (int d = 0; d <= 9; ++d)
                        ways[len][s + d] += cur;
                }
            }
        }

        void buildGood() {
            for (int rem = 0; rem <= kMaxLen; ++rem) {
                for (int pref = 0; pref <= kMaxSum; ++pref) {
                    long cnt = 0;
                    for (int tail = 0; tail <= 9 * rem; ++tail) {
                        if (pref + tail <= kMaxSum && isPrime[pref + tail]) {
                            cnt += ways[rem][tail];
                        }
                    }
                    good[rem][pref] = cnt;
                }
            }
        }

        long countUpto(long x) {
            String s = Long.toString(x);
            int sum = 0;
            long ans = 0;

            for (int i = 0; i < s.length(); ++i) {
                int d = s.charAt(i) - '0';
                int rem = s.length() - i - 1;
                for (int dig = 0; dig < d; ++dig) {
                    ans += good[rem][sum + dig];
                }
                sum += d;
            }
            if (isPrime[sum])
                ++ans;
            return ans;
        }
    }

    static long nthValue(long n, DigitPrimeDP dp) {
        long lo = 1;
        long hi = 1;
        while (dp.countUpto(hi) < n)
            hi <<= 1;

        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (dp.countUpto(mid) >= n)
                hi = mid;
            else
                lo = mid + 1;
        }
        return lo;
    }

    public static String solve() {
        DigitPrimeDP dp = new DigitPrimeDP();
        return Long.toString(nthValue(10000000000000000L, dp));
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}