<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>





int _ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); return 0; }();

class Solution {
public:
    std::vector<int> px;
public:
    void load_palindromes() {
        for(int i = 1; i < 20001; ++i) {
            std::string straight = std::to_string(i);
            std::string reversed = std::string(straight.rbegin(), straight.rend());
            int const last = reversed.back() - '0';
            int const size = (straight.size() + reversed.size());
            int const fnum = std::stoi(straight + reversed);
            if(is_prime(fnum)) { px.push_back(fnum); }
            straight.pop_back();
            int const bnum = std::stoi(straight + reversed);
            if(is_prime(bnum)) { px.push_back(bnum); }
        }
    }
    
    bool is_prime(int n) {
        int k = 2;
        while(k*k <= n) { if((n % k) == 0) { return false; } k += 1; }
        return n > 1;
    }    
    
    int find_left(std::vector<int> const &nums, int target) {
        int const n = nums.size();
        int left = 0, right = n, mid = 0;
        while(left < right) {
            mid = left + ((right - left) >> 1);
            if(nums[mid] < target) {
                left  = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    
    int primePalindrome(int n) {
        load_palindromes();
        std::ranges::sort(px);
        return px[find_left(px, n)];
    }
};
14500