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

/////////////////////////////// Preface
// utility functions
using ll = long long;
using ld = long double;
using ull = unsigned long long;

// typedef
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> ti3;
typedef tuple<int, int, int, int> ti4;
typedef tuple<int, int, int, int, int> ti5;
typedef tuple<ll, ll, ll> tll3;
typedef tuple<ll, ll, ll, ll> tll4;
typedef tuple<ll, ll, ll, ll, ll> tll5;
typedef vector<pll> vpll;
typedef array<int, 3> ai3;
typedef array<ll, 3> all3;
typedef array<ll, 4> all4;
typedef array<ll, 5> all5;
typedef vector<all3> vall3;
typedef vector<all4> vall4;
typedef vector<all5> vall5;
typedef pair<ld, ld> pld;
typedef vector<pld> vpld;
typedef vector<ld> vld;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef deque<ll> dqll;
typedef deque<pll> dqpll;
typedef pair<string, string> pss;
typedef vector<pss> vpss;
typedef vector<string> vs;
typedef vector<vs> vvs;
typedef unordered_set<ll> usll;
// typedef unordered_set<pll, PairHash> uspll;
typedef unordered_map<ll, ll> umll;
// typedef unordered_map<pll, ll, PairHash> umpll;

// macros
#define X first
#define Y second

void _p(int x) { cout << x; }
void _p(long x) { cout << x; }
void _p(long long x) { cout << x; }
void _p(unsigned x) { cout << x; }
void _p(unsigned long x) { cout << x; }
void _p(unsigned long long x) { cout << x; }
void _p(float x) { cout << x; }
void _p(double x) { cout << x; }
void _p(long double x) { cout << x; }
void _p(char x) { cout << '\'' << x << '\''; }
void _p(const char *x) { cout << '\"' << x << '\"'; }
void _p(const string &x) { cout << '\"' << x << '\"'; }
void _p(bool x) { cout << (x ? "true" : "false"); }
template <typename A> void _p(const A &x) {
    bool first = true;
    cout << '{';
    for (const auto &i : x) {
        cout << (first ? "" : ","), _p(i);
        first = false;
    }
    cout << '}';
}
template <typename A, typename B> void _p(const pair<A, B> &p) {
    cout << '(';
    _p(p.first);
    cout << ',';
    _p(p.second);
    cout << ')';
}
template <typename... A> void _p(const tuple<A...> &t) {
    bool first = true;
    cout << '(';
    apply(
        [&first](const auto &...args) {
            ((cout << (first ? "" : ","), _p(args), first = false), ...);
        },
        t);
    cout << ')';
}
void _pt(const initializer_list<ll> &t) { _p(tuple(t)); }
template <typename T> void _p(stack<T> s) {
    vector<T> debugVector;
    while (!s.empty()) {
        T t = s.top();
        debugVector.push_back(t);
        s.pop();
    }
    reverse(debugVector.begin(), debugVector.end());
    _p(debugVector);
}
template <typename T> void _p(queue<T> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.front();
        debugVector.push_back(t);
        q.pop();
    }
    _p(debugVector);
}
template <typename T, typename... U> void _p(priority_queue<T, U...> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.top();
        debugVector.push_back(t);
        q.pop();
    }
    _p(debugVector);
}
void __p() { cout << "]\n"; }
template <typename Head, typename... Tail>
void __p(const Head &H, const Tail &...T) {
    _p(H);
    if (sizeof...(T))
        cout << ", ";
    __p(T...);
}
#ifndef ONLINE_JUDGE
#define debug(...)                                                             \
    cout << "Line:" << __LINE__ << " [" << #__VA_ARGS__ << "] = [";            \
    __p(__VA_ARGS__);
#else
#define debug(...)
#endif

#define rep(i, m, n) for (ll i = m; i < n; i++)
#define rrep(i, m, n) for (ll i = m; i > n; i--)

template <class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> inline bool chmin(T &a, T b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

template <typename T> void _pn(T &&t) { cout << t << "\n"; }
template <typename T> void _pv(vector<T> v) {
    ll n = v.size();
    rep(i, 0, n) {
        _p(v[i]);
        if (i + 1 != n)
            cout << ' ';
    }
    cout << endl;
}
template <typename T> void _pvv(vector<vector<T>> v) {
    ll n = v.size();
    rep(i, 0, n) _pv(v[i]);
}
template <typename T> void _pvln(vector<T> v) {
    ll n = v.size();
    rep(i, 0, n) cout << v[i] << endl;
}

// Mods
long long mod = 1e9 + 7;

long long mod_add(long long a, long long b) { return (a + b) % mod; }

long long mod_sub(long long a, long long b) { return (a + mod - b) % mod; }

long long mod_mul(long long a, long long b) { return a * b % mod; }

long long mod_pow(long long b, long long p) {
    if (!p)
        return 1;
    long long half = mod_pow(b, p / 2);
    return mod_mul(mod_mul(half, half), p % 2 ? b : 1LL);
}

long long mod_inv(long long b) { return mod_pow(b, mod - 2); }

long long mod_factorial(long long x) {
    if (x < 2)
        return 1;
    return mod_mul(x, mod_factorial(x - 1));
}

ll unset(ll num, ll mask) { return num ^ (num & mask); }
/////////////////////////////// Preface

/*
1.  ex
2.  req
3.  bf

4.  obs

5.  opt

6.  impl

7.  ts

*/

bool is_palin(ll i) {
    auto s = to_string(i);
    int n = s.size();
    rep(i, 0, n / 2) if (s[i] != s[n - 1 - i]) return false;
    return true;
}

class Solution {
  public:
    int superpalindromesInRange(string left, string right) {
        int ans = 0;
        ll l = stoll(left), r = stoll(right);

        auto ok = [&](auto &s) {
            auto i = stoll(s);
            ll sqr = i * i;
            return l <= sqr && sqr <= r && is_palin(sqr);
        };

        rep(fi, 1, 3e4) {
            auto f = to_string(fi);
            string b(f.rbegin(), f.rend());
            auto e = f + b, o = f + b.substr(1);
            ans += ok(e);
            // if(ok(e)){
            //     _p(e);
            //     _pt({stoll(e), stoll(e) * stoll(e)});
            // }
            ans += ok(o);
            // if(ok(o)){
            //     _p(o);
            //     _pt({stoll(o), stoll(o) * stoll(o)});
            // }
        }
        return ans;
    }
};
20000