# Let's say a positive integer is a superpalindrome if it is a palindrome, and it is also the square of a palindrome.
#
# Now, given two positive integers L and R (represented as strings), return the number of superpalindromes in the
# inclusive range [L, R].
#
#
#
# Example 1:
#
# Input: L = "4", R = "1000"
# Output: 4
# Explanation: 4, 9, 121, and 484 are superpalindromes.
# Note that 676 is not a superpalindrome: 26 * 26 = 676, but 26 is not a palindrome.
#
#
# Note:
#
# 1 <= len(L) <= 18
# 1 <= len(R) <= 18
# L and R are strings representing integers in the range [1, 10^18).
# int(L) <= int(R)
import math


class Solution(object):
    def superpalindromesInRange_tle(self, L, R):
        """
        :type L: str
        :type R: str
        :rtype: int
        """

        def isPalindrome(t):
            s, n = 0, t
            while t:
                s = s * 10 + t % 10
                t /= 10

            return s == n

        res = 0
        start, end = int(int(L) ** .5), int(int(R) ** .5)

        for i in xrange(start - 1, end + 1):
            if isPalindrome(i) and isPalindrome(i * i) and int(L) <= i * i <= int(R):
                print i
                res += 1

        return res

    def superpalindromesInRange(self, L, R):
        """
        :type L: str
        :type R: str
        :rtype: int
        """
        res = 0
        start, end = int(int(L) ** .5), int(int(R) ** .5)

        def isPalindrome(t):
            s, n = 0, t
            while t:
                s = s * 10 + t % 10
                t /= 10

            return s == n

        # yield n digits palindrom, if n is 3, produce 121, 212, etc.
        def genPalindrome(lower, upper):
            # if n is odd
            # check how many digit of lower and upper sqare root boundary have, for ex, if lower = 100
            # then it should have at least 3 digit, if upper is 10000, then it should have 5 digits
            # if lower is 0, it should have at least 1 digit
            n1, n2, res = int(math.log10(lower)) + 1 if lower > 0 else 1, int(math.log10(upper)) + 1, []

            for n in xrange(n1, n2 + 1):
                # if n is odd, then we should have something like 12321
                if n & 1:
                    # if t == 1, we can choose 1->9
                    t = n / 2
                    if not t:
                        res.extend(range(1, 10))
                        continue
                    # a is the mid
                    for a in xrange(0, 10):
                        # assume n == 7, then t = 3, so we can choose from 100 - 999, for ex, 8742478
                        # so lower : 10 **(3-1) = 100, upper : 10 * 3 = 1000
                        for m in xrange(10 ** (t - 1), 10 ** t):
                            s = int(str(m) + str(a) + str(m)[::-1])
                            if lower <= s <= upper:
                                res.append(s)

                else:  # if n is even, so should have 123321
                    t = n / 2
                    for m in xrange(10 ** (t - 1), 10 ** t):
                        s = int(str(m) + str(m)[::-1])
                        if lower <= s <= upper:
                            res.append(s)

            return res

        cans = genPalindrome(start - 1, end + 1)
        for i in cans:
            k = i * i
            if int(L) <= k <= int(R) and isPalindrome(k):
                res += 1

        return res

    def superpalindromesInRange2(self, L, R):
        """
        :type L: str
        :type R: str
        :rtype: int
        """
        L, R = int(L), int(R)
        # since Len(L) < 18 and len(R) < 18, its sqaure root is 10**9, assume k is the half palindrome, k||K' = P,
        # it could be something like
        # 1234321 or 12344321 , k = 1234, k would be < 10 ** 5, this is how the MAGIC comes from
        MAGIC = 100000

        def reverse(x):
            ans = 0
            while x:
                ans = 10 * ans + x % 10
                x /= 10
            return ans

        def is_palindrome(x):
            return x == reverse(x)

        ans = 0

        # count odd length
        for k in xrange(MAGIC):
            s = str(k)  # Eg. s = '1234'
            t = s + s[-2::-1]  # t = '1234321'
            v = int(t) ** 2
            if v > R: break
            if v >= L and is_palindrome(v):
                ans += 1

        # count even length
        for k in xrange(MAGIC):
            s = str(k)  # Eg. s = '1234'
            t = s + s[::-1]  # t = '12344321'
            v = int(t) ** 2
            if v > R: break
            if v >= L and is_palindrome(v):
                ans += 1

        return ans


if __name__ == '__main__':
    # print Solution().superpalindromesInRange("4", "1000")
    # print Solution().superpalindromesInRange("1020762146323", "142246798855636")
    print Solution().superpalindromesInRange("1", "2")
    # print Solution().superpalindromesInRange_tle("1020762146323", "142246798855636")
