Fair and Square (Large 1)

리틀 존은 회문을 좋아해서 회문을 공정한 수라고 부른다. 회문은 앞에서 읽어도 뒤에서 읽어도 같은 정수다. 6, 11, 121은 회문이고 10, 12, 223, 2244는 회문이 아니다. 앞에 붙는 0은 따지지 않으므로 010 = 10 같은 표기로 10이 회문이 되지는 않는다.

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

구간이 주어지면 그 구간 안에 fair and square 수가 몇 개 있는지 세는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개의 줄에 각각 두 정수 $A$와 $B$가 공백으로 구분되어 주어진다. $A$와 $B$는 리틀 존이 살펴보는 구간의 양 끝이다.

제한

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

각 테스트 케이스마다 한 줄에 "Case #x: y" 형식으로 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 $A \le n \le B$를 만족하는 fair and square 수 $n$의 개수다.