공정한 제곱수 (Large2)

리틀 존은 회문수를 좋아해서 회문수를 공정한 수라고 부른다. 회문수는 앞에서 읽으나 뒤에서 읽으나 똑같은 정수다. 6, 11, 121은 회문수이고 10, 12, 223, 2244는 회문수가 아니다. 수를 적을 때 맨 앞의 0은 쓰지 않으므로, 010은 10과 같은 수로 보고 회문수로 치지 않는다.

존은 제곱수에도 관심이 생겨서 공정한 제곱수를 이렇게 정의했다. 어떤 수가 회문수이면서 동시에 회문수의 제곱이면 그 수는 공정한 제곱수다. 1, 9, 121은 각각 1, 3, 11의 제곱이고 그 자신도 회문수이므로 공정한 제곱수다. 반면 16, 22, 676은 공정한 제곱수가 아니다. 16은 회문수가 아니고, 22는 제곱수가 아니며, 676은 회문수이자 제곱수이지만 26의 제곱인데 26이 회문수가 아니다.

구간이 하나 주어지면 그 안에 공정한 제곱수가 몇 개 있는지 세어라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개의 줄에 각각 구간의 양 끝 값인 정수 $A$와 $B$가 공백으로 구분되어 주어진다.

제한

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

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 $A$ 이상 $B$ 이하인 공정한 제곱수의 개수다.