# Solution Lũy thừa
link đề: https://oj.vnoi.info/problem/power

## Tóm đề
- dòng đầu đề cho t là số test case
- mỗi t dòng tiếp theo sẽ có 2 số l và r
- yêu cầu tìm số k lớn nhất sao cho thỏa mãn $l\le x^k\le r$
## Hướng giải
vì $2^{40}>10^{12}$ nên ta có thể cho chạy for k từ 39 trở xuống
dùng binary search để kiểm tra xem liệu có $x$ tồn tại thỏa mãn điều kiện ko
nếu không thì hạ k xuống và tiếp tục kiểm tra
## Code mẫu

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    for(int j=1;j<=t;j++){
        //for j cho mỗi test case
        long long l,r,ans=1;
        cin>>l>>r;
        long long lo,hi,mid,b=2;
        for(long long i=39;i>1;i--){
            //for i thử mỗi số mũ k

            while(pow(b,i)<r)b*=2;
            //xác định biên trên hi
            hi=b;lo=2;//biên dưới lo
            while(lo<hi){
                //binary search
                mid=(lo+hi)/2;
                
                if(pow(mid,i)>r)hi=mid;
                //ko -1 tránh mất số
                //lí do vì ko check mid trước :b
                else if(pow(mid,i)<l)lo=mid+1;
                //+1 tránh lặp vô hạn
                else{
                    //tìm đc k lớn nhất
                    ans=i;
                    break;
                }
            }
            if(ans!=1)break;
            //đã có kết quả, dừng lặp
        }
        cout<<"Case #"<<j<<": "<<ans<<endl;
    }
}