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

typedef long long ll;
class Solution {
public:
    vector<ll> ps;
    int ret=0;
    ll L=0;
    ll R=0;
    bool check(ll v){
        string s1=to_string(v);
        string s2=s1;
        reverse(begin(s2),end(s2));
        ll num=stoll(s1+s2);
        if(num<=1e9){
            num*=num;
            s2=to_string(num);
            int l=0;
            int r=s2.size()-1;
            while(l<=r&&s2[l]==s2[r]){
                l++;
                r--;
            }
            if(l>r&&L<=num&&num<=R)ret++;
        }
        s2=s1.substr(0,(int)s1.size()-1);
        reverse(begin(s2),end(s2));
        num=stoll(s1+s2);
        if(num*num<=R){
            num*=num;
            s2=to_string(num);
            int l=0;
            int r=s2.size()-1;
            while(l<=r&&s2[l]==s2[r]){
                l++;
                r--;
            }
            if(l>r&&L<=num&&num<=R)ret++;
        }else return false;
        return true;
    }
    int superpalindromesInRange(string leftS, string rightS) {
        L=stoll(leftS);
        R=stoll(rightS);
        for(ll i=1;i<1e5;i++){
            if(!check(i))break;
        }
        // sort(begin(ps),end(ps));
        // for(auto v:ps)cout<<v<<" ";
        // cout<<endl;
        // int n=ps.size();
        // int l=0;
        // int r=n-1;
        // int mid;
        // int count1=0;
        // while(l<=r){
        //     mid=(l+r)/2;
        //     if(ps[mid]<left){
        //         count1=mid+1;
        //         l=mid+1;
        //     }else r=mid-1;
        // }
        // int count2=0;
        // l=0;
        // r=n-1;
        // while(l<=r){
        //     mid=(l+r)/2;
        //     if(ps[mid]<=right){
        //         count2=mid+1;
        //         l=mid+1;
        //     }else r=mid-1;
        // }
        // int ret=count2-count1;
        return ret;
    }
};
43600