완전세제곱수

세제곱근이 정수인 정수를 완전세제곱수라고 한다. 1, 8, 27, 64, 125는 완전세제곱수이고 9, 25, 113은 완전세제곱수가 아니다.

양의 정수 $A$와 $B$가 주어질 때, $A$ 이상 $B$ 이하인 완전세제곱수의 개수를 구하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $T$는 $1 \le T \le 10^5$인 양의 정수다.

다음 $T$개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄에는 두 정수 $A$와 $B$가 공백 하나로 구분되어 주어지며, $1 \le A \le B \le 2 \times 10^9$이다.

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