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

set<int> ms;

class Solution {
public:

    Solution() {
        if(!ms.empty()) {
            return;
        }
        string t = "";
        ms.insert(2);
        ms.insert(3);
        ms.insert(5);
        ms.insert(7);
        for( int ii=1; ii<9; ii++) {
            t.push_back('0');
            if(ii<2) {
                continue;
            }
            for( char ch='1'; ch<='9'; ch+=2) {
                t[0] = t.back() = ch;
                gen( 1, ii-2, t);
            }
        }
        t.push_back('0');
        t[0] = t.back() = '1';
        gen( 0, t.length()-1, t);
    }

    bool isPrime( int v) {
        for( int i=2; i*i<=v; i++) {
            if(v%i==0) {
                return false;
            }
        }
        return true;
    }

    void gen( int startId, int endId, string & t) {
        if(startId>endId) {
            int v = stoi(t);
            if(isPrime(v)) {
                ms.insert(v);
            }
        } else {
            for( char ch='0'; ch<='9'; ch++) {
                t[startId] = t[endId] = ch;
                gen( startId+1, endId-1, t);
            }
        }
    }

    int primePalindrome(int n) {
        return *ms.lower_bound(n);
    }
};
9400