공정하고 제곱인 수

Little John는 회문을 좋아하며, 회문이 공정하다고 생각한다(이는 멋있다는 뜻의 근사한 표현이다). 회문은 앞에서부터 읽으나 뒤에서부터 읽으나 같은 정수일 뿐이다. 따라서 6, 11, 121는 모두 회문이지만, 10, 12, 223, 2244는 회문이 아니다(010=10이기는 하지만, 어떤 수가 회문인지 판단할 때 앞에 붙은 영은 고려하지 않는다).

그는 최근 제곱수에도 관심을 갖게 되었고, 공정하고 제곱인 수를 정의했다. 이는 회문이면서 동시에 회문의 제곱인 수이다. 예를 들어, 1, 9, 121는 각각 회문이면서 1, 3, 11의 제곱이므로 공정하고 제곱인 수이다. 반면 16, 22, 676는 공정하고 제곱인 수가 아니다. 16은 회문이 아니고, 22는 제곱수가 아니며, 676은 회문이자 제곱수이기는 하지만 회문이 아닌 26의 제곱이다.

이제 그는 더 큰 공정하고 제곱인 수를 찾고 싶어 한다. 주어진 Little John가 탐색 중인 구간에 공정하고 제곱인 수가 몇 개 있는지 알려 주어, 그가 그 수들을 모두 찾은 때를 알 수 있게 하는 것이 당신의 과제이다.

이 문제 풀기

일반적으로 Google Code Jam 문제에는 1 소형 입력 하나와 1 대형 입력 하나가 있다. 이 문제에는 1 소형 입력 하나와 2 대형 입력 두 개가 있다. 소형 입력을 해결하고 나면 두 대형 입력 중 어느 것이든 다운로드할 수 있다. 평소와 마찬가지로 소형 입력은 시간 페널티를 받고 다시 시도할 수 있지만, 각 대형 입력에는 단 한 번만 도전할 수 있다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

소형 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ T ≤ 100. 1 ≤ A ≤ B ≤ 1000.

첫 번째 대형 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ T ≤ 10000. 1 ≤ A ≤ B ≤ $10^{14}$.

두 번째 대형 데이터 세트 (테스트 세트 3 - 비공개)

1 ≤ T ≤ 1000. 1 ≤ A ≤ B ≤ $10^{100}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 Little John가 살펴보는 구간의 양 끝점인 두 정수 A와 B가 주어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 (1)부터 시작하는 테스트 케이스 번호이고, y는 A 이상 B 이하인 공정하고 제곱인 수의 개수이다.