<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 {
public:
        bool isPalindrome(string str)
        {
                int low=0,high=str.length()-1;
                while(low<=high)
                {
                        if(str[low]!=str[high])
                                return false;
                        low++;
                        high--;
                }
                return true;
        }
        long long int formPalindrome(int i, int j)
        {
                long long int x=i;
                int rev=0;              
                if(j==-1)  
                {
                        while(i>0)
                        {
                                int last=i%10;
                                i/=10;
                                x=x*10+last;
                        }
                        return x;
                }
                x=x*10+j;
                while(i>0)
                {
                        int last=i%10;
                        i/=10;
                        x=x*10+last;
                }
                return x;        
        }
        int superpalindromesInRange(string left, string right) 
        {
                long long int leftt=stoll(left);
                long long int rightt=stoll(right);                
                vector<long long int> palindromes;
                for(int i=1;i<10;i++)
                        palindromes.push_back(i);                
                for(int i=1;i<10000;i++)   
                {
                        palindromes.push_back(formPalindrome(i,-1));         
                        for(int j=0;j<=9;j++)
                                palindromes.push_back(formPalindrome(i,j)); 
                }                
                int count=0;
                for(long long int i=0;i<palindromes.size();i++)
                {
                        long long int no=palindromes[i];
                        long long int sq=no*no;                        
                        if(leftt<=sq and sq<=rightt and isPalindrome(to_string(sq))) 
                                count++;
                }
                return count;
        }
};
147700