시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6 5 3 100.000%

문제

A perfect cube is an integer whose cube root is also an integer. For example 1, 8, 27, 64, 125, etc. are examples of perfect cubes but 9, 25 and 113 are not. Given two positive integers A and B, your task is to calculate the number of perfect cubes in the given range between A and B inclusively. 

입력

The first line has a positive integer T, T <= 100000, denoting the number of test cases. This is followed by each test case per line.

Each test case consists of a single line containing two integers A and B separated by a single space. 1 ≤ A ≤ B ≤ 2,000,000,000.

출력

For each test case, output contains a line in the format Case #x: M, where x is the case number (starting from 1) and M is the number of perfect cubes in the given range between A and B inclusive. 

예제 입력

10
1 2000000000
42 1011
170 1254
963 2504
282 2430
996 4262
392 2361
293 3308
719 8614
772 5458

예제 출력

Case #1: 1259
Case #2: 7
Case #3: 5
Case #4: 4
Case #5: 7
Case #6: 7
Case #7: 6
Case #8: 8
Case #9: 12
Case #10: 8

힌트