perfect power 是指可以表示成x^y（x>1,y>1）的数，给一个区间[A,B]求由这个区间的所有perfect能组成多少种不同形态的二叉查找树。
预处理出范围内的所有perfect power和范围内的所有卡特兰数。二分搜索个数。
注意到ｘ和ｙ都是大于１的。而题目的范围是１０^１０，那么只要枚举ｘ到１０^５多一点即可。
然后算了一下每个数之多只要算３０次左右就行了。如此来看，暴力是完全可以选出所有的ｐｅｒｆｅｃｔ ｐｏｗｅｒ的。
对这些数排序，然后二分搜索区间ＡＢ的上下界即可。
一、在看别人代码的时候看到一个非常屌的二分。
int lower(ll x) {
if(x<T[0])return 0;
if(x>=T[T.size()-1])return T.size();
int l=0,r=T.size()-1;
int mid;
while(l<=r) {
mid=(l+r)>>1;
if(T[mid]==x)return mid+1;
if(x>T[mid])l=mid+1;
else r=mid-1;
}
return min(r,mid)+1;
}
比如要查找Ｔ中在区间[A,B]内的数的个数，那么结果就是lower(B)-lower(A-1);
二、卡特兰数。
Ci=(4*i-2)/(i+1)*Ci-1
这个题用到的卡特兰数大约有十万，要求的是卡特兰数mod１００００００００７（质数）。
求的时候直接模肯定是不行的，得要求逆元。
三、乘法逆元
乘法逆元。一个数ａ，如果存在一个数ｎ使得ａ×ｎ＝１（ ｍｏｄ ｐ）。那么称ｎ为ａ对ｐ的乘法逆元。
存在乘法逆元的必要条件是ｇｃｄ（ａ，ｐ）＝１；
两种简单求法。
１、由费马小定理知，ｎ=ａ ^ （euler（ｐ））－１，ｅｕｌｅｒ是欧拉函数值。特殊的，素数ｐ的欧拉函数值是ｐ－１；
２、同余，上述式子相当于求ａ×ｎ＋ｐ×ｙ＝１中的ｎ的值。用扩展欧几里得即可求得，如果结果小于０，一直加ｐ直到为正为止。
到这里，这个题算是做完了。快速幂什么的就不提了。
#define mod 100000007
const ll maxT=11000000000LL;
ll PowMod(ll a,ll n){
if(n==1)return a;
if(n==0)return 1;
ll tmp=PowMod(a,n>>1)%mod;
tmp=(tmp*tmp)%mod;
if(n&1)tmp=(tmp*a)%mod;
return tmp;
}
vector<ll> sel;
void ini2(){
sel.clear();
for(ll i=2;i<maxn;i++){
ll tmp=i*i;
if(tmp>maxT)break;
while(tmp<=maxT){
sel.pb(tmp);
tmp*=i;
}
}
sort(sel.begin(),sel.end());
sel.erase(unique(sel.begin(),sel.end()),sel.end());
}
int upper(ll x){
int l=0,r=sel.size()-1;
int mid;
while(l<r){
mid=(l+r)>>1;
if(sel[mid]>x)r=mid;
else l=mid+1;
}
return r;
}
int lower(ll x){
int l=0,r=sel.size()-1;
int mid;
while(l<r){
mid=(l+r)>>1;
if(sel[mid]>=x)r=mid;
else l=mid+1;
}
return r;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1,y=0;return a;
}
ll gcd=exgcd(b,a%b,x,y);
ll temp=x;x=y;
y=temp-(a/b)*y;
return gcd;
}
ll C[110000];
int main(){
//cout<<PowMod(3,mod)<<endl;
ini2();
memset(C,0,sizeof(C));
C[0]=0;
C[1]=1;
for(ll i=2;i<109000;i++){
ll x,y;
exgcd(i+1,mod,x,y);
C[i]=(((C[i-1]%mod)*((4*i-2)%mod))%mod*(x%mod+mod)%mod)%mod;
}
int T;
scanf("%d",&T);
for(int tt=1;tt<=T;tt++){
ll a,b;
scanf("%lld%lld",&a,&b);
int tmpa=lower(a);
int tmpb=upper(b);
ll ans=C[tmpb-tmpa];
printf("Case %d: %lld\n",tt,ans);
}
return 0;
}