Cho ~l~, ~r~ sao cho ~2 \leq l \leq r \leq 10^{12}~. Tìm số ~k~ nguyên dương lớn nhất sao cho tồn tại số nguyên dương ~x~ để ~l \leq x^k \leq r~.

Input

Dòng đầu tiên là số lượng test.

Mỗi dòng tiếp theo chứa hai số nguyên ~l, r~ biểu thị một test.

Output

Đối với mỗi test in ra "Case #" ~+~ số hiệu test ~+~ ": " ~+~ số ~k~ lớn nhất tìm được.

Sample Input

4
5 20
10 12
2 100
1000000000000 1000000000000

Sample Output

Case #1: 4
Case #2: 1
Case #3: 6
Case #4: 12