All submissions for this problem are available.
Ash ketchum wants to be the greatest poke'mon master ever but for this he has to win the poke'mon league.In order to win the league he has to choose a roster of poke'mons for the battle. Ash has caught a lot of poke'mon and is therefore confused which poke'mons to take with him to the league. To help him decide this he goes to professor Oak.
In order to help Ash professor Oak assigns integers to Ash's poke'mon .Prof Oak likes palindromes, and thinks them to be fair. A palindrome is just an integer that reads the same backwards and forwards - so 6, 11 and 121 are all palindromes, while 10, 12, 223 and 2244 are not (even though 010=10, we don't consider leading zeroes when determining whether a number is a palindrome).
He recently became interested in squares as well, and formed the definition of a fair and square number - it is a number that is a palindrome and the square of a palindrome at the same time. For instance, 1, 9 and 121 are fair and square(being palindromes and squares, respectively, of 1, 3 and 11).
Now to select poke'mons for Ash's roster he needs your help. Your task is, given an interval Prof Oak is searching through, to tell him how many fair and square numbers are there in the interval, so he knows when he has found them all. Help him find all the fair and square numbers (poke'mon) and Ash in winning the league and becoming the greatest poke'mon master of all time.
The first line of the input gives the number of test cases, T. T lines follow. Each line contains two integers, A and B - the endpoints of the interval Professor Oak is looking at.
For each test case, output one line containing "y", y is the number of fair and square numbers greater than or equal to A and smaller than or equal to B.
- 1 ≤ T ≤ 1000
- 1 ≤ A,B ≤ 10^100
Input: 3 1 4 10 120 100 1000 Output: 2 0 2
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.