문제

완전 세제곱수는 세제곱근 역시 정수인 정수입니다. 예를 들어 1, 8, 27, 64, 125 등은 완전 세제곱수이지만 9, 25, 113은 아닙니다. 두 양의 정수 A와 B가 주어졌을 때, 당신은 A부터 B까지 완전 세제곱수의 개수를 계산해야 합니다.

입력

첫 줄에 테스트 케이스의 수를 나타내며 T <= 100000를 만족하는 양의 정수 T가 입력됩니다. 다음 각 줄에 테스트 케이스가 주어집니다.

각 테스트 케이스는 두 정수 A와 B가 하나의 공백으로 구분되어 한 줄에 주어집니다. 1 <= A <= B <= 2000000000.

출력

각 테스트 케이스에 대해, 한 줄에 x가 (1부터 시작되는) 케이스의 번호를 나타내고 M이 A부터 B까지 완전 세제곱수의 개수를 나타내는 Case #x: M 형식을 출력합니다.