<p>Given an integer n, return <em>the smallest <strong>prime palindrome</strong> greater than or equal to </em><code>n</code>.</p>

<p>An integer is <strong>prime</strong> if it has exactly two divisors: <code>1</code> and itself. Note that <code>1</code> is not a prime number.</p>

<ul>
	<li>For example, <code>2</code>, <code>3</code>, <code>5</code>, <code>7</code>, <code>11</code>, and <code>13</code> are all primes.</li>
</ul>

<p>An integer is a <strong>palindrome</strong> if it reads the same from left to right as it does from right to left.</p>

<ul>
	<li>For example, <code>101</code> and <code>12321</code> are palindromes.</li>
</ul>

<p>The test cases are generated so that the answer always exists and is in the range <code>[2, 2 * 10<sup>8</sup>]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> n = 6
<strong>Output:</strong> 7
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> n = 8
<strong>Output:</strong> 11
</pre><p><strong class="example">Example 3:</strong></p>
<pre><strong>Input:</strong> n = 13
<strong>Output:</strong> 101
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>8</sup></code></li>
</ul>

/// @author Huy
/// @date   15:11:37 20/07/2024
#include <iostream>

#ifdef HUY_DEBUG
#include "E:/code/library/debug.h"
using namespace std;

#else
#define dbg(...) 42
#endif

bool isPalindrome(const std::string &s) {
    for (int l = 0, r = (int) s.size() - 1; l < r; ++l, --r) {
        if (s[l] != s[r]) return false;
    }
    return true;
}

template<typename T> bool isPrime(T n) {
    if (n == 2 || n == 3) return true;
    if (n <= 1 || n % 2 == 0 || n % 3 == 0) return false;
    for (T i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

class Solution {
public:
    int primePalindrome(int n) {
        const int maxn = 1e4 + 10;
        std::set<long long> se;
        for (int i = 1; i <= maxn; ++i) {
            {
                std::string s1 = std::to_string(i);
                std::string s2 = s1; s2.pop_back();
                std::reverse(s2.begin(), s2.end());
                long long k = std::stol(s1 + s2);
                if (k >= n && isPrime(k)) se.insert(k);
            }
            {
                std::string s1 = std::to_string(i);
                std::string s2 = s1;
                std::reverse(s2.begin(), s2.end());
                long long k = std::stol(s1 + s2);
                if (k >= n && isPrime(k)) se.insert(k);
            }
        }
        return *se.begin();
    }
};

#ifdef HUY_DEBUG
signed main() {
    Solution sol;
    int n; std::cin >> n;
    std::cout << sol.primePalindrome(n) << '\n';
    return 0;
}
#endif
13500