Fair and Square (Large 1)

Little John likes palindromes and calls them fair. A palindrome is an integer that reads the same forwards and backwards, so 6, 11 and 121 are palindromes while 10, 12, 223 and 2244 are not. Leading zeroes do not count, so writing 010 = 10 does not make 10 a palindrome.

Little John also became interested in squares, so he defined a fair and square number: a number that is a palindrome and at the same time the square of a palindrome. For example 1, 9 and 121 are fair and square, because each one is a palindrome and each one is the square of 1, 3 and 11 respectively. On the other hand 16, 22 and 676 are not fair and square. 16 is not a palindrome, 22 is not a square, and 676 is a palindrome and a square, but its square root 26 is not a palindrome.

Given an interval, count how many fair and square numbers lie inside it.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains two integers $A$ and $B$ separated by a space, the endpoints of one interval Little John is looking at.

Limits

• $1 \le T \le 10000$
• $1 \le A \le B \le 10^{14}$

For each test case, print one line in the form "Case #x: y", where $x$ is the test case number starting from 1 and $y$ is the number of fair and square numbers $n$ with $A \le n \le B$.