Fair and Square (Large2)

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. Numbers are written without leading zeros, so 010 is the same number as 10 and does not count as a palindrome.

John also became interested in squares, and defined a fair and square number this way: a number is fair and square if it is a palindrome and it is the square of a palindrome. For example 1, 9 and 121 are fair and square, because each one is a palindrome and they are the squares of 1, 3 and 11. 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 both a palindrome and a square but it is the square of 26, which is not a palindrome.

Given one interval, count the fair and square numbers inside it.

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

Limits

• $1 \le T \le 1000$
• $1 \le A \le B \le 10^{100}$

For each test case, print one line of 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 that are greater than or equal to $A$ and less than or equal to $B$.