Read problems statements in  Mandarin Chinese  and  Russian. 
Recently Chef become very much interested in perfect squares. We all know Chef and his weird interests. Anyways Chef will be soon writing his masters thesis on perfect squares revealing what-not-known properties of perfect squares.
While doing his research, he happened to be confronted with some interesting perfect squares. These prefect squares consists only of digits which are themselves perfect squares. 0, 1, 4 and 9 are such digits. These are called perfect digits.
As we all know Chef also has habit of asking too many questions, he is asking- given two numbers a and b, how many perfect squares exists between these two numbers inclusive, that contains only perfect digits. 
Input:
First line of input will contains T, number of test cases. Then T lines follows, each containing two positive integers a and b.
Constraints:
T ≤ 500
1≤ a ≤ b ≤ 10000000000 
Output:
For each input, output number of perfect digit squares between given numbers. 
Sample

----- Sample Input 1 ------ 
2
1 10
100 10000
----- Sample Output 1 ------ 
3
9

Source: codechef | Difficulty: MEDIUM
Tags: Preprocessing

Complete search


Solutions:
from bisect import *
table = [0, 1, 4, 9, 49, 100, 144, 400, 441, 900, 1444, 4900, 9409, 10000, 10404, 11449, 14400, 19044, 40000, 40401, 44100, 44944, 90000, 144400, 419904, 490000, 491401, 904401, 940900, 994009, 1000000, 1004004, 1014049, 1040400, 1100401, 1144900, 1440000, 1904400, 1940449, 4000000, 4004001, 4040100, 4410000, 4494400, 9000000, 9909904, 9941409, 11909401, 14010049, 14040009, 14440000, 19909444, 40411449, 41990400, 49000000, 49014001, 49140100, 49999041, 90440100, 94090000, 94109401, 99400900, 99940009, 100000000, 100040004, 100140049, 100400400, 101404900, 101949409, 104040000, 104919049, 110040100, 111049444, 114041041, 114490000, 144000000, 190440000, 194044900, 400000000, 400040001, 400400100, 404010000, 404090404, 409941009, 414000409, 414041104, 441000000, 449440000, 490091044, 900000000, 990990400, 991494144, 994140900, 1190940100, 1401004900, 1404000900, 1409101444, 1444000000, 1449401041, 1490114404, 1990944400, 4014109449, 4019940409, 4041144900, 4199040000, 4900000000, 4900140001, 4901400100, 4914010000, 4914991449, 4941949401, 4999904100, 9044010000, 9409000000, 9409194001, 9410940100, 9900449001, 9940090000, 9994000900, 9999400009, 10000000000]
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	aa = bisect_left(table, a)
	bb = bisect_right(table, b)
	print(bb - aa)


from math import sqrt as S, ceil as upar, floor as neeche

def sahi(n):
	if str(n).count('0') + str(n).count('1') + str(n).count('4') + str(n).count('9') == len(str(n)):
		return True
	return False
p = 10 ** 5 + 9
pre = [0] * p
for i in range(1, p):
	curr = i * i
	pre[i] = pre[i - 1] + sahi(curr)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	b = int(S(b))
	a = int(S(a - 1))
	print(pre[b] - pre[a])


n = int(input())
x = ['2', '3', '5', '6', '7', '8']
lm = []
for i in range(1, 10 ** 5 + 1):
	flag = 0
	for j in x:
		if j in str(i ** 2):
			flag = 1
			break
	if flag == 0:
		lm.append(i ** 2)
for i in range(n):
	(a, b) = map(int, input().split())
	c = 0
	for k in lm:
		if k >= a and k <= b:
			c += 1
	print(c)


def is_digit_square(n):
	while n > 0:
		if n % 10 not in [0, 1, 4, 9]:
			return False
		n //= 10
	return True

def lower_bound(x):
	low = 0
	high = len(digit_squares)
	while low < high:
		mid = (low + high) // 2
		if digit_squares[mid] < x:
			low = mid + 1
		else:
			high = mid
	return low
digit_squares = []
for i in range(1, 10 ** 5):
	if is_digit_square(i ** 2):
		digit_squares.append(i ** 2)
t = int(input())
for _ in range(t):
	(a, b) = (int(i) for i in input().split())
	lb = lower_bound(a)
	ub = lower_bound(b + 1)
	if ub == len(digit_squares):
		print(ub - lb + 1)
	else:
		print(ub - lb)


IN = lambda : int(input())
l1 = ['1', '0', '4', '9']

def fk(t):
	s = str(t)
	for i in s:
		if i in l1:
			pass
		else:
			return False
	return True
l = []
for i in range(100005):
	if fk(i * i):
		l.append(i * i)
for _ in range(IN()):
	c = 0
	(n, k) = map(int, input().split())
	for j in l:
		if j >= n and j <= k:
			c += 1
	print(c)


a = [str(i * i) for i in range(1, 10 ** 5 + 1)]
s = ['2', '3', '5', '6', '7', '8']
g = []
for i in a:
	f = 0
	for j in s:
		if j in i:
			f = 1
			break
	if f == 0:
		g.append(int(i))
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(len([i for i in g if a <= i <= b]))


import bisect
t = int(input())
temp = {1: 1, 4: 2, 9: 3, 49: 4, 100: 5, 144: 6, 400: 7, 441: 8, 900: 9, 1444: 10, 4900: 11, 9409: 12, 10000: 13, 10404: 14, 11449: 15, 14400: 16, 19044: 17, 40000: 18, 40401: 19, 44100: 20, 44944: 21, 90000: 22, 144400: 23, 419904: 24, 490000: 25, 491401: 26, 904401: 27, 940900: 28, 994009: 29, 1000000: 30, 1004004: 31, 1014049: 32, 1040400: 33, 1100401: 34, 1144900: 35, 1440000: 36, 1904400: 37, 1940449: 38, 4000000: 39, 4004001: 40, 4040100: 41, 4410000: 42, 4494400: 43, 9000000: 44, 9909904: 45, 9941409: 46, 11909401: 47, 14010049: 48, 14040009: 49, 14440000: 50, 19909444: 51, 40411449: 52, 41990400: 53, 49000000: 54, 49014001: 55, 49140100: 56, 49999041: 57, 90440100: 58, 94090000: 59, 94109401: 60, 99400900: 61, 99940009: 62, 100000000: 63, 100040004: 64, 100140049: 65, 100400400: 66, 101404900: 67, 101949409: 68, 104040000: 69, 104919049: 70, 110040100: 71, 111049444: 72, 114041041: 73, 114490000: 74, 144000000: 75, 190440000: 76, 194044900: 77, 400000000: 78, 400040001: 79, 400400100: 80, 404010000: 81, 404090404: 82, 409941009: 83, 414000409: 84, 414041104: 85, 441000000: 86, 449440000: 87, 490091044: 88, 900000000: 89, 990990400: 90, 991494144: 91, 994140900: 92, 1190940100: 93, 1401004900: 94, 1404000900: 95, 1409101444: 96, 1444000000: 97, 1449401041: 98, 1490114404: 99, 1990944400: 100, 4014109449: 101, 4019940409: 102, 4041144900: 103, 4199040000: 104, 4900000000: 105, 4900140001: 106, 4901400100: 107, 4914010000: 108, 4914991449: 109, 4941949401: 110, 4999904100: 111, 9044010000: 112, 9409000000: 113, 9409194001: 114, 9410940100: 115, 9900449001: 116, 9940090000: 117, 9994000900: 118, 9999400009: 119, 10000000000: 120}
arr = [1, 4, 9, 49, 100, 144, 400, 441, 900, 1444, 4900, 9409, 10000, 10404, 11449, 14400, 19044, 40000, 40401, 44100, 44944, 90000, 144400, 419904, 490000, 491401, 904401, 940900, 994009, 1000000, 1004004, 1014049, 1040400, 1100401, 1144900, 1440000, 1904400, 1940449, 4000000, 4004001, 4040100, 4410000, 4494400, 9000000, 9909904, 9941409, 11909401, 14010049, 14040009, 14440000, 19909444, 40411449, 41990400, 49000000, 49014001, 49140100, 49999041, 90440100, 94090000, 94109401, 99400900, 99940009, 100000000, 100040004, 100140049, 100400400, 101404900, 101949409, 104040000, 104919049, 110040100, 111049444, 114041041, 114490000, 144000000, 190440000, 194044900, 400000000, 400040001, 400400100, 404010000, 404090404, 409941009, 414000409, 414041104, 441000000, 449440000, 490091044, 900000000, 990990400, 991494144, 994140900, 1190940100, 1401004900, 1404000900, 1409101444, 1444000000, 1449401041, 1490114404, 1990944400, 4014109449, 4019940409, 4041144900, 4199040000, 4900000000, 4900140001, 4901400100, 4914010000, 4914991449, 4941949401, 4999904100, 9044010000, 9409000000, 9409194001, 9410940100, 9900449001, 9940090000, 9994000900, 9999400009, 10000000000]
for _ in range(t):
	(a, b) = map(int, input().split())
	flag1 = 0
	flag2 = 0
	if a in temp and b in temp:
		ans = temp[b] - temp[a]
	elif a in temp:
		lb2 = arr[bisect.bisect_left(arr, b, 0, len(arr)) - 1]
		ans = temp[lb2] - temp[a]
	elif b in temp:
		lb1 = arr[bisect.bisect_left(arr, a, 0, len(arr))]
		ans = temp[b] - temp[lb1]
	else:
		lb1 = arr[bisect.bisect_left(arr, a, 0, len(arr))]
		lb2 = arr[bisect.bisect_left(arr, b, 0, len(arr)) - 1]
		ans = temp[lb2] - temp[lb1]
	ans += 1
	print(ans)


import math

def verifyPerfectDigit(n):
	n = int(n)
	while n > 0:
		x = int(n % 10)
		if x != 0 and x != 1 and (x != 4) and (x != 9):
			return 0
		n = int(n / 10)
	return 1

def createArray():
	arr = []
	for i in range(1, 100001):
		if verifyPerfectDigit(i * i) == 1:
			arr.append(i * i)
	return arr

def main():
	t = int(input())
	arr = createArray()
	while t:
		str = input()
		a = 0
		b = 0
		count = 0
		(str1, str2) = str.split(' ')
		for i in range(0, len(str1)):
			a = a * 10 + int(str1[i])
		for i in range(0, len(str2)):
			b = b * 10 + int(str2[i])
		for i in range(0, len(arr)):
			if arr[i] >= a and arr[i] <= b:
				count += 1
		print(count)
		t -= 1
main()


l = []
s = {'0', '1', '4', '9'}
for i in range(0, 100001):
	ans = i * i
	if set(str(ans)).issubset(s):
		l.append(ans)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	n = len(l)
	s = 0
	for i in l:
		if a <= i <= b:
			s += 1
	print(s)


t = int(input())
ans = []
for j in range(10 ** 5 + 1):
	flag = 0
	num = str(j * j)
	for i in range(len(num)):
		if num[i] != '0' and num[i] != '1' and (num[i] != '4') and (num[i] != '9'):
			flag = 1
			break
	if flag == 0:
		ans.append(j * j)
for I in range(t):
	(a, b) = [int(i) for i in input().split()]
	count = 0
	for i in range(len(ans)):
		if ans[i] >= a and ans[i] <= b:
			count += 1
	print(count)


import math
n = 10 ** 10
arr = []
for i in range(1, 1 + int(math.ceil(math.sqrt(n)))):
	s = str(i * i)
	flag = True
	if '2' in s or '3' in s or '5' in s or ('6' in s) or ('7' in s) or ('8' in s):
		flag = False
	if flag:
		arr.append(int(s))
t = int(input())
while t:
	t -= 1
	(a, b) = map(int, input().split())
	c = 0
	for i in arr:
		if i >= a and i <= b:
			c += 1
	print(c)


from math import *
count = []
for i in range(10 ** 5 + 5):
	q = 0
	for j in str(i ** 2):
		if j not in ['0', '1', '4', '9']:
			q = 1
			break
	if q == 0:
		count.append(i ** 2)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	c = 0
	for i in count:
		if i >= n and i <= m:
			c += 1
		elif i > m:
			break
	print(c)


n = 0
arr = []
while n * n <= 10000000000:
	z = n * n
	flag = 0
	while z > 0:
		k = int(z % 10)
		if k != 0 and k != 1 and (k != 4) and (k != 9):
			flag = 1
			break
		z //= 10
	if flag == 0:
		arr.append(n * n)
	n += 1
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	count = 0
	for i in range(len(arr)):
		if a <= arr[i] <= b:
			count += 1
	print(count)


import math
import sys

def _int():
	return int(sys.stdin.readline())

def _ints():
	return map(int, sys.stdin.readline().split())

def _intarr():
	return list(map(int, sys.stdin.readline().split()))

def _str():
	return sys.stdin.readline()

def _strarr():
	return sys.stdin.readline().split()

def is_perfect(n):
	perfect = True
	while n != 0:
		r = n % 10
		if r not in [0, 1, 4, 9]:
			perfect = False
			break
		n = n // 10
	return perfect
mem = [0] * 100001
c = 0
for i in range(1, len(mem)):
	if is_perfect(i * i):
		c += 1
	mem[i] = c
t = _int()
for _ in range(t):
	(a, b) = _ints()
	ra = int(math.ceil(math.sqrt(a)))
	rb = int(math.floor(math.sqrt(b)))
	print(mem[rb] - mem[ra - 1])


try:
	t = int(input())
	l = ['0', '1', '4', '9']
	m = []
	c = 0
	s = 0
	j = 0
	while j <= 1000002:
		s = str(j * j)
		for k in s:
			if k not in l:
				c = 0
				break
			else:
				c = 1
		if c == 1:
			m.append(s)
		j = j + 1
	for _ in range(t):
		count = 0
		(a, b) = map(int, input().split())
		for i in m:
			if int(i) >= a and int(i) <= b:
				count += 1
		print(count)
except:
	pass


import math

def fun(n):
	l = ['0', '1', '4', '9']
	s = str(n)
	for k in range(len(s)):
		if s[k] not in l:
			return False
	return True
l1 = []
for i in range(1000000):
	if fun(i ** 2) == True:
		l1.append(i ** 2)
for it in range(int(input())):
	count = 0
	lst = list(map(int, input().split()))
	a = lst[0]
	b = lst[1]
	for j in l1:
		if j >= a and j <= b:
			count += 1
	print(count)


noOfTestCases = int(input())
result = [0, 1, 4, 9, 49, 100, 144, 400, 441, 900, 1444, 4900, 9409, 10000, 10404, 11449, 14400, 19044, 40000, 40401, 44100, 44944, 90000, 144400, 419904, 490000, 491401, 904401, 940900, 994009, 1000000, 1004004, 1014049, 1040400, 1100401, 1144900, 1440000, 1904400, 1940449, 4000000, 4004001, 4040100, 4410000, 4494400, 9000000, 9909904, 9941409, 11909401, 14010049, 14040009, 14440000, 19909444, 40411449, 41990400, 49000000, 49014001, 49140100, 49999041, 90440100, 94090000, 94109401, 99400900, 99940009, 100000000, 100040004, 100140049, 100400400, 101404900, 101949409, 104040000, 104919049, 110040100, 111049444, 114041041, 114490000, 144000000, 190440000, 194044900, 400000000, 400040001, 400400100, 404010000, 404090404, 409941009, 414000409, 414041104, 441000000, 449440000, 490091044, 900000000, 990990400, 991494144, 994140900, 1190940100, 1401004900, 1404000900, 1409101444, 1444000000, 1449401041, 1490114404, 1990944400, 4014109449, 4019940409, 4041144900, 4199040000, 4900000000, 4900140001, 4901400100, 4914010000, 4914991449, 4941949401, 4999904100, 9044010000, 9409000000, 9409194001, 9410940100, 9900449001, 9940090000, 9994000900, 9999400009, 10000000000]
while noOfTestCases != 0:
	(lower, upper) = list(map(int, input().split()))
	res = 0
	for i in result:
		if i >= lower and i <= upper:
			res += 1
		elif i > upper:
			break
	print(res)
	noOfTestCases -= 1


t = int(input())
l = ['2', '3', '5', '6', '7', '8']
k = []
for j in range(1, 10 ** 5 + 1):
	flag = 0
	for c in l:
		if c in str(j ** 2):
			flag = 1
			break
	if flag == 0:
		k.append(j ** 2)
for i in range(t):
	(a, b) = list(map(int, input().split()))
	count = 0
	for m in k:
		if a <= m <= b:
			count += 1
	print(count)


import math
import collections
lst = ['0', '1', '4', '9']
for i in range(4, 100001):
	n = str(i * i)
	l = len(n)
	d = collections.Counter(n)
	k = d['0'] + d['1'] + d['4'] + d['9']
	if k == l:
		lst.append(n)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	count = 0
	for num in lst:
		if int(num) >= a and int(num) <= b:
			count += 1
	print(count)


def check(n):
	for j in str(n):
		if j not in ['1', '0', '4', '9']:
			return False
	return True
t = int(input())
maxi = 100001
sq = []
for i in range(maxi):
	s = i * i
	if check(s):
		sq.append(s)
for _ in range(t):
	(l, u) = map(int, input().split())
	count = 0
	for i in sq:
		if l <= i and i <= u:
			count += 1
	print(count)


def main():
	import math
	T = int(input())
	output = list()
	squaredigits = {'0', '1', '4', '9'}
	sqrt_beginning = 1
	sqrt_end = math.ceil(math.sqrt(10000000000))
	x = 0
	counter = 0
	listcounter = list()
	while x <= sqrt_end:
		square = x * x
		string_square = str(square)
		flag = -1
		for digit in string_square:
			if digit not in squaredigits:
				flag = 0
				break
		if flag == -1:
			counter = counter + 1
		listcounter.append(counter)
		x = x + 1
	for i in range(0, T):
		line = input()
		linelist = line.split()
		a = int(linelist[0])
		b = int(linelist[1])
		sqrt_a = math.ceil(math.sqrt(a))
		sqrt_b = math.ceil(math.sqrt(b))
		output.append(listcounter[sqrt_b] - listcounter[sqrt_a - 1])
	for x in output:
		print(x)
main()


import math
ans = [0] * 100001
for i in range(1, 100001):
	s = str(i ** 2)
	ans[i] = ans[i - 1]
	for j in s:
		if j not in {'0', '1', '4', '9'}:
			break
	else:
		ans[i] += 1
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	(a, b) = (math.ceil(a ** 0.5), math.floor(b ** 0.5))
	print(ans[b] - ans[a - 1])


from math import sqrt
lst = []

def perfectsquarelst():
	aa = 1
	bb = 100000
	for i in range(aa, bb + 1):
		num = str(i * i)
		perfect = True
		for d in num:
			if d in ['2', '3', '5', '6', '7', '8']:
				perfect = False
		if perfect:
			lst.append(i * i)
T = int(input())
perfectsquarelst()
while T > 0:
	T -= 1
	count = 0
	(a, b) = map(int, input().split(' '))
	for k in lst:
		if k >= a and k <= b:
			count += 1
	print(count)


import bisect

def is_digit_square(n):
	while n > 0:
		if n % 10 not in [0, 1, 4, 9]:
			return False
		n //= 10
	return True
digit_squares = []
for i in range(1, 10 ** 5):
	if is_digit_square(i ** 2):
		digit_squares.append(i ** 2)
t = int(input())
for _ in range(t):
	(a, b) = (int(i) for i in input().split())
	lower_bound = bisect.bisect_left(digit_squares, a)
	upper_bound = bisect.bisect_right(digit_squares, b)
	if upper_bound == len(digit_squares):
		print(upper_bound - lower_bound + 1)
	else:
		print(upper_bound - lower_bound)


def lower_bound(aux, x):
	l = 0
	r = len(aux) - 1
	while l < r:
		mid = l + (r - l) // 2
		if aux[mid] >= x:
			r = mid
		else:
			l = mid + 1
	return l
aux = []
for i in range(1, 100000 + 1):
	t = str(i * i)
	if t.count('0') + t.count('1') + t.count('4') + t.count('9') == len(t):
		aux.append(int(t))
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	ans = lower_bound(aux, b) - 1 - lower_bound(aux, a) + 1
	if b in aux:
		ans += 1
	print(ans)


import math
l = []
for i in range(1, 100001):
	m = i * i
	temp = 1
	while m:
		if m % 10 != 0 and m % 10 != 1 and (m % 10 != 4) and (m % 10 != 9):
			temp = 0
			break
		m = m // 10
	if temp == 1:
		l.append(i)
for i in range(int(input())):
	(a, b) = map(int, input().split())
	s = 0
	a1 = math.ceil(a ** 0.5)
	b1 = int(b ** 0.5)
	m = 0
	n = -1
	for j in range(len(l)):
		if l[j] <= b1:
			m = j
		if l[j] < a1:
			n = j
	print(m - n)


import math
t = int(input())
l = [0] * 1000001
for i in range(1, 1000001):
	x = str(i * i)
	if x.count('1') + x.count('0') + x.count('4') + x.count('9') == len(x):
		l[i] = l[i - 1] + 1
	else:
		l[i] = l[i - 1]
for i in range(t):
	(a, b) = map(int, input().split())
	(a, b) = (math.ceil(pow(a, 0.5)), math.ceil(pow(b, 0.5)))
	print(l[b] - l[a - 1])


n = 10 ** 5 + 1
l = []
for i in range(1, n):
	x = i ** 2
	s = str(x)
	q = 0
	for j in s:
		if j != '0' and j != '1' and (j != '4') and (j != '9'):
			q = 1
			break
	if q == 0:
		l.append(x)
t = int(input())
while t > 0:
	(a, b) = map(int, input().split())
	x = y = 0
	for i in range(120):
		if l[i] >= b:
			x = i
			break
	if l[i] > b:
		x -= 1
	for j in range(120):
		if l[j] >= a:
			y = j
			break
	print(x - y + 1)
	t -= 1


from math import ceil, floor, sqrt

def solve(n):
	x = [0, 1, 4, 9]
	while n != 0:
		if n % 10 in x:
			n //= 10
		else:
			return 0
	return 1
ans = [0] * 100001
for i in range(1, 100001):
	ans[i] = solve(i * i)
for i in range(1, 100001):
	ans[i] += ans[i - 1]
t = int(input())
for _ in range(t):
	(l, r) = map(int, input().split())
	l = ceil(sqrt(l))
	r = floor(sqrt(r))
	print(ans[r] - ans[l - 1])


t = int(input())
lst = []
j = 0
while j * j <= 10000000000:
	z = j * j
	flag = 0
	while z > 0:
		k = int(z % 10)
		if k != 0 and k != 1 and (k != 4) and (k != 9):
			flag = 1
			break
		z = z / 10
	if flag == 0:
		lst.append(j * j)
	j = j + 1
while t > 0:
	t -= 1
	(a, b) = map(int, input().split())
	count = 0
	for i in range(len(lst)):
		if lst[i] >= a and lst[i] <= b:
			count += 1
	print(count)


from sys import stdin
awsSquares = [1, 4, 9, 49, 100, 144, 400, 441, 900, 1444, 4900, 9409, 10000, 10404, 11449, 14400, 19044, 40000, 40401, 44100, 44944, 90000, 144400, 419904, 490000, 491401, 904401, 940900, 994009, 1000000, 1004004, 1014049, 1040400, 1100401, 1144900, 1440000, 1904400, 1940449, 4000000, 4004001, 4040100, 4410000, 4494400, 9000000, 9909904, 9941409, 11909401, 14010049, 14040009, 14440000, 19909444, 40411449, 41990400, 49000000, 49014001, 49140100, 49999041, 90440100, 94090000, 94109401, 99400900, 99940009, 100000000, 100040004, 100140049, 100400400, 101404900, 101949409, 104040000, 104919049, 110040100, 111049444, 114041041, 114490000, 144000000, 190440000, 194044900, 400000000, 400040001, 400400100, 404010000, 404090404, 409941009, 414000409, 414041104, 441000000, 449440000, 490091044, 900000000, 990990400, 991494144, 994140900, 1190940100, 1401004900, 1404000900, 1409101444, 1444000000, 1449401041, 1490114404, 1990944400, 4014109449, 4019940409, 4041144900, 4199040000, 4900000000, 4900140001, 4901400100, 4914010000, 4914991449, 4941949401, 4999904100, 9044010000, 9409000000, 9409194001, 9410940100, 9900449001, 9940090000, 9994000900, 9999400009, 10000000000]
T = int(stdin.readline().strip())
while T > 0:
	[l, r] = [int(n) for n in stdin.readline().strip().split()]
	low = 0
	high = len(awsSquares) - 1
	while low < high:
		mid = int((low + high) / 2)
		if awsSquares[mid] < l:
			low = mid + 1
		else:
			high = mid
	start = low
	low = 0
	high = len(awsSquares) - 1
	while low < high:
		mid = int((low + high + 1) / 2)
		if awsSquares[mid] > r:
			high = mid - 1
		else:
			low = mid
	end = low
	if start <= end:
		print(end - start + 1)
	else:
		print('0')
	T -= 1


def check(i):
	s = str(i)
	for x in s:
		if x == '1' or x == '0' or x == '4' or (x == '9'):
			pass
		else:
			return False
	return True
precompute = list()
for i in range(100002):
	if check(i ** 2):
		precompute.append(i ** 2)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	cnt = 0
	for x in precompute:
		if x >= a and x <= b:
			cnt += 1
	print(cnt)


op = [0]
count = 0
for j in range(1, 100001):
	z = str(j * j)
	if len(z) == z.count('0') + z.count('1') + z.count('4') + z.count('9'):
		count += 1
	op.append(count)
t = int(input())
for i in range(0, t):
	(a, b) = input().strip().split()
	a = int(a)
	b = int(b)
	if pow(a, 1 / 2) == int(pow(a, 1 / 2)):
		a = int(pow(a, 1 / 2))
	else:
		a = int(pow(a, 1 / 2)) + 1
	b = int(pow(b, 1 / 2))
	print(op[b] - op[a - 1])


perfect_sqaures = []
perfect_nums = {'0', '1', '4', '9'}

def is_perfect_square(num):
	num = set(str(num))
	if len(num - perfect_nums) == 0:
		return True
	return False
for i in range(10 ** 5 + 1):
	num = i * i
	if is_perfect_square(num):
		perfect_sqaures.append(num)
perfect_sqaures_len = len(perfect_sqaures)

def find_perfect_squares_count(num):
	start = 0
	end = perfect_sqaures_len - 1
	while start <= end:
		middle = (start + end) // 2
		if perfect_sqaures[middle] == num or (perfect_sqaures[middle] < num and (middle + 1 == perfect_sqaures_len or perfect_sqaures[middle + 1] > num)):
			return middle + 1
		elif perfect_sqaures[middle] < num:
			start = middle + 1
		else:
			end = middle - 1
import math
tests = int(input())
for i in range(tests):
	(a, b) = map(int, input().split())
	remove = find_perfect_squares_count(a - 1)
	total = find_perfect_squares_count(b)
	print(total - remove)


perf = []

def findvalid():
	for i in range(1, 10 ** 5 + 1):
		square = i ** 2
		s = set(str(square))
		for digit in s:
			if digit == '1' or digit == '0' or digit == '4' or (digit == '9'):
				cool = True
			else:
				cool = False
				break
		if cool:
			perf.append(square)
findvalid()
from bisect import bisect_left as bl
for i in range(int(input())):
	allowed = [0, 1, 4, 9]
	(a, b) = [int(x) for x in input().split()]
	left = bl(perf, a)
	right = bl(perf, b)
	if perf[right] == b:
		right += 1
	print(right - left)


from bisect import bisect_left, bisect_right

def prfsqr(a, b):
	sqr = []
	chk = [0, 1, 4, 9]
	for i in range(a, b, 1):
		k = i ** 2
		if k <= b:
			prf = True
			k = str(k)
			for j in k:
				if int(j) not in chk:
					prf = False
					break
			if prf:
				sqr.append(int(k))
		else:
			break
	return sqr
sqr = prfsqr(1, 10 ** 10)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	leftind = bisect_left(sqr, a)
	rightind = bisect_right(sqr, b)
	print(rightind - leftind)


import os
import math

def checknum(num):
	while num > 0:
		temp = num % 10
		if temp != 1 and temp != 4 and (temp != 9) and (temp != 0):
			return 0
		num = num // 10
	return 1
t = int(input())
avalues = []
bvalues = []
for i in range(t):
	(a, b) = input().strip().split()
	a = int(a)
	b = int(b)
	avalues.append(a)
	bvalues.append(b)
amin = min(avalues)
bmax = max(bvalues)
squares = []
begin = math.ceil(math.sqrt(amin))
end = math.floor(math.sqrt(bmax))
for j in range(begin, end + 1):
	num = j * j
	if checknum(num) == 1:
		squares.append(num)
for i in range(t):
	count = 0
	for j in range(len(squares)):
		if squares[j] >= avalues[i]:
			m = j
			while m < len(squares) and squares[m] <= bvalues[i]:
				count += 1
				m += 1
			break
	print(count)


import sys
import math
from time import time
from itertools import permutations, combinations
import collections
import functools
from fractions import gcd, Fraction
import string
import operator
import bisect

class timed(object):

	def __init__(self, func):
		self.func = func

	def __call__(self, *args):
		t1 = time()
		ret = self.func(*args)
		dif_time = time() - t1
		print('%s: returned %s in %f seconds' % (self.func.__name__, ret, dif_time))
		return ret

def comp(f1, f2, *args):
	t1 = time()
	r1 = f1(*args) if f1 is not None else None
	t2 = time()
	r2 = f2(*args) if f2 is not None else None
	t3 = time()
	res = '%5s: %s in %f\n%5s: %s in %f' % (f1.__name__ if f1 is not None else None, r1, t2 - t1, f2.__name__ if f2 is not None else None, r2, t3 - t2)
	if r1 != r2:
		dr = '!! DIFFERENT RESULTS !!'
		res = dr + '\n' + res + '\n' + dr
	print(res)

def alg(start, end):
	root_start = int(math.sqrt(start))
	root_end = int(math.sqrt(end))
	count = 0
	for root in range(root_start, root_end + 1):
		sq = root * root
		if all([int(a) in [0, 1, 4, 9] for a in str(sq)]):
			count += 1
	return count

def alg2(start, end):
	perfect_squares = [1, 4, 9, 49, 100, 144, 400, 441, 900, 1444, 4900, 9409, 10000, 10404, 11449, 14400, 19044, 40000, 40401, 44100, 44944, 90000, 144400, 419904, 490000, 491401, 904401, 940900, 994009, 1000000, 1004004, 1014049, 1040400, 1100401, 1144900, 1440000, 1904400, 1940449, 4000000, 4004001, 4040100, 4410000, 4494400, 9000000, 9909904, 9941409, 11909401, 14010049, 14040009, 14440000, 19909444, 40411449, 41990400, 49000000, 49014001, 49140100, 49999041, 90440100, 94090000, 94109401, 99400900, 99940009, 100000000, 100040004, 100140049, 100400400, 101404900, 101949409, 104040000, 104919049, 110040100, 111049444, 114041041, 114490000, 144000000, 190440000, 194044900, 400000000, 400040001, 400400100, 404010000, 404090404, 409941009, 414000409, 414041104, 441000000, 449440000, 490091044, 900000000, 990990400, 991494144, 994140900, 1190940100, 1401004900, 1404000900, 1409101444, 1444000000, 1449401041, 1490114404, 1990944400, 4014109449, 4019940409, 4041144900, 4199040000, 4900000000, 4900140001, 4901400100, 4914010000, 4914991449, 4941949401, 4999904100, 9044010000, 9409000000, 9409194001, 9410940100, 9900449001, 9940090000, 9994000900, 9999400009, 10000000000]
	res = filter(lambda x: start <= x and end >= x, perfect_squares)
	return len(list(res))

def main():
	data = sys.stdin
	nb = int(data.readline())
	for icase in range(nb):
		(start, end) = map(int, data.readline().split())
		res = alg2(start, end)
		print(res)
main()


def fun(argc):
	for i in range(4, 100001):
		k = i * i
		s = str(k)
		flag = True
		for j in range(len(s)):
			if s[j] in argc:
				pass
			else:
				flag = False
				break
		if flag == True:
			argc.append(s)
t = int(input())
lst = ['0', '1', '4', '9']
fun(lst)
for i in range(t):
	(n, m) = map(int, input().split())
	flag1 = True
	flag2 = True
	j = 0
	k = 0
	for i in range(len(lst)):
		if flag1 == False and flag2 == False:
			break
		if int(lst[i]) >= n and flag1 == True:
			j = i
			flag1 = False
		if int(lst[i]) >= m and flag2 == True:
			if int(lst[i]) == m:
				k = i
			else:
				k = i - 1
			flag2 = False
	print(k - j + 1)


def lucky_check(n):
	for i in range(len(n)):
		if n[i] not in '1049':
			return False
	return True
array = []
for i in range(1, 100001):
	if lucky_check(str(i * i)):
		array.append(i * i)
final = []
for i in range(len(array) - 1):
	final.append([array[i], array[i + 1] - 1])

def find(a):
	if a == 10000000000:
		return 120
	elif a == 0:
		return 0
	else:
		i = 0
		found = False
		while not found:
			p = final[i]
			if a <= p[1] and a >= p[0]:
				found = True
			i += 1
		return i
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(find(b) - find(a - 1))


import math
power_list = []
for i in range(1, 100001):
	curr = i * i
	is_valid = True
	while curr:
		if curr % 10 in [0, 1, 4, 9]:
			curr //= 10
		else:
			is_valid = False
			break
	if is_valid:
		power_list.append(i)
for _ in range(int(input())):
	(left, rite) = [int(x) for x in input().split()]
	cnts = 0
	left = math.ceil(left ** 0.5)
	rite = int(rite ** 0.5)
	m = 0
	n = -1
	for j in range(len(power_list)):
		if power_list[j] <= rite:
			m = j
		if power_list[j] < left:
			n = j
	print(m - n)


import os, sys, io, math
from array import *
from math import *
from bisect import *
from heapq import *
from functools import *
from itertools import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
l = ['1', '0', '4', '9']

def f(t):
	s = str(t)
	for i in s:
		if i in l:
			pass
		else:
			return False
	return True
r = []
for i in range(100002):
	if f(i * i):
		r.append(i * i)
for _ in range(IN()):
	(a, b) = map(int, input().split())
	c = 0
	for i in r:
		if i >= a and i <= b:
			c += 1
	print(c)


l = []
l1 = ['0', '1', '4', '9']
for i in range(1, 100001):
	s = str(i * i)
	if any((j not in l1 for j in s)):
		c = 1
	else:
		l.append(i * i)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	ans = 0
	for i in l:
		if i >= a and i <= b:
			ans += 1
	print(ans)


maximum = int(10000000000 ** 0.5)
perfect = {'0', '1', '4', '9'}
pn = []
for i in range(1, maximum + 1):
	if set(str(i * i)).union(perfect) == perfect:
		pn.append(i * i)
t = int(input())
for u in range(t):
	(a, b) = map(int, input().split())
	count = 0
	for i in range(len(pn)):
		if pn[i] > b:
			break
		elif pn[i] >= a:
			count += 1
	print(count)
	print()


import bisect

def perfect_digit(n):
	ar = [2, 3, 5, 6, 7, 8]
	while n > 0:
		if n % 10 in ar:
			return False
		n //= 10
	return True
ar = []
for i in range(1, 10 ** 5 + 1):
	cur = i * i
	if perfect_digit(cur):
		ar.append(cur)
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	(right, left) = (bisect.bisect_left(ar, y), bisect.bisect_left(ar, x))
	if ar[right] > y:
		right -= 1
	if ar[left] < x:
		left += 1
	print(right - left + 1)


t = int(input())
arr = []
for i in range(10 ** 5 + 5):
	te = str(i * i)
	st = 0
	for j in range(len(te)):
		if te[j] != '1' and te[j] != '4' and (te[j] != '9') and (te[j] != '0'):
			st = 1
			break
	if st == 0:
		arr.append(i * i)
length = len(arr)
while t:
	t -= 1
	(a, b) = map(int, input().split())
	ans = 0
	for i in range(length):
		if arr[i] >= a and arr[i] <= b:
			ans += 1
	print(ans)


def consists_of_perfect_digits(number):
	while number != 0:
		digit = number % 10
		if digit not in [0, 1, 4, 9]:
			return False
		number //= 10
	return True

def count_perfect_squares(perfect_digits, a, b):
	num_perf_sq = 0
	i = 0
	while i < len(perfect_digits) and perfect_digits[i] <= b:
		if perfect_squares[i] >= a and perfect_squares[i] <= b:
			num_perf_sq += 1
		i += 1
	return num_perf_sq
perfect_squares = []
for i in range(100000 + 1):
	perf_sq = i * i
	if consists_of_perfect_digits(perf_sq):
		perfect_squares.append(perf_sq)
T = int(input())
for t in range(T):
	(a, b) = map(int, input().split())
	print(count_perfect_squares(perfect_squares, a, b))