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

class Solution:
    def primePalindrome(self, n: int) -> int:
        def is_palindrome(x):
            s = str(x)
            return s == s[::-1]

        def is_prime(x):
            if x < 2:
                return False
            if x == 2:
                return True
            if x % 2 == 0:
                return False
            for i in range(3, int(math.sqrt(x)) + 1, 2):
                if x % i == 0:
                    return False
            return True

        # Generate palindrome candidates
        def generate_palindromes():
            for i in range(1, 10):  # Single digit palindromes
                yield i
            for length in range(1, 6):  # Palindromes up to 10^8
                # Odd length palindromes
                for root in range(10**(length - 1), 10**length):
                    s = str(root)
                    yield int(s + s[-2::-1])
                # Even length palindromes
                for root in range(10**(length - 1), 10**length):
                    s = str(root)
                    yield int(s + s[::-1])

        # Iterate over palindromes and find the smallest prime palindrome >= n
        for palindrome in generate_palindromes():
            if palindrome >= n and is_prime(palindrome):
                return palindrome

        return -1  # This should never happen with the given constraints


16300