<p>Let&#39;s say a positive integer is a <strong>super-palindrome</strong> if it is a palindrome, and it is also the square of a palindrome.</p>

<p>Given two positive integers <code>left</code> and <code>right</code> represented as strings, return <em>the number of <strong>super-palindromes</strong> integers in the inclusive range</em> <code>[left, right]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> left = &quot;4&quot;, right = &quot;1000&quot;
<strong>Output:</strong> 4
<strong>Explanation</strong>: 4, 9, 121, and 484 are superpalindromes.
Note that 676 is not a superpalindrome: 26 * 26 = 676, but 26 is not a palindrome.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> left = &quot;1&quot;, right = &quot;2&quot;
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= left.length, right.length &lt;= 18</code></li>
	<li><code>left</code> and <code>right</code> consist of only digits.</li>
	<li><code>left</code> and <code>right</code> cannot have leading zeros.</li>
	<li><code>left</code> and <code>right</code> represent integers in the range <code>[1, 10<sup>18</sup> - 1]</code>.</li>
	<li><code>left</code> is less than or equal to <code>right</code>.</li>
</ul>

class Solution:
    def superpalindromesInRange(self, left: str, right: str) -> int:
        l = floor(int(left) ** 0.5)
        r = floor(int(right) ** 0.5) + 1
        pc = 0
        def inc_str(x):
            return str(int(x) + 1)
        def is_pali(x):
            return x == x[::-1] and int(left) <= int(x) <= int(right)
        def next_pali(x):
            x = [x for x in x]
            l = len(x)
            if all([x == "9" for x in x]):
                return "".join(["1"] + ["0" for _ in range(len(x) - 1)] + ["1"])
            elif len(x) == 1:
                return inc_str(x[0])
            m = m2 = l // 2
            if l % 2 == 0:
                m -= 1
            for i in range(l // 2):
                if not x[m - i] == "9":
                    if i != 0 or l % 2 == 0:
                        for j in [m - i, m2 + i]:
                            x[j] = inc_str(x[j])
                        return "".join(x)
                    else:
                        x[m] = inc_str(x[m])
                        return "".join(x)
                else:
                    while x[m - i - 1] == "9":
                        i += 1
                    for j in range(m - i, m2 + i + 1):
                        x[j] = "0"
                    x[m - i - 1] = inc_str(x[m - i - 1])
                    x[m2 + i + 1] = inc_str(x[m2 + i + 1])
                    return "".join(x)
        l = str(l)
        l2 = len(l) // 2
        if len(l) % 2 == 0:
            l = l[:l2] + l[:l2][::-1]
        else:
            l = l[:l2 + 1] + l[:l2][::-1]
        while(int(l) < r):
            pc += is_pali(str(int(l) ** 2))
            l = next_pali(l)
        return pc
16800