#include<string.h>
#include<time.h>
typedef long long LL;
const int N=2;
int st;
typedef struct mat{
LL M[N][N];
mat(){//memset(M,0,sizeof(M));
M[0][0]=M[0][1]=M[1][0]=M[1][1]=0;
}
mat(LL *p){
for(int i=0;i<N;i++) for(int j=0;j<N;j++) M[i][j]=*p++;
}
//void write(){for(int i=0;i<N;i++,puts("")) for(int j=0;j<N;j++) printf("%I64d ",M[i][j]);}
}mat;
LL e[2][2]={{1,0},{0,1}},a1[2][2]={{1,1},{1,0}},a2[2][2]={{2,1},{1,1}},a4[2][2]={{5,3},{3,2}};
mat E(&e[0][0]),A1(&a1[0][0]),A2(&a2[0][0]),A4(&a4[0][0]);
const LL mod=1000000007;
mat add(mat a,mat b,LL c){
mat ret;
LL *p=&a.M[0][0],*q=&b.M[0][0];
for(int i=0;i<N;i++) for(int j=0;j<N;j++) ret.M[i][j]=(*p+++*q++)%c;
return ret;
}
mat mul(mat a,mat b,LL c){
mat ret;
//LL *p=&ret.M[0][0];
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
ret.M[i][j]=(ret.M[i][j]+a.M[i][k]*b.M[k][j])%c;
//*p=(*p+a.M[i][k]*b.M[k][j])%c;
return ret;
}
mat fast(mat a,LL b,LL c){
if(b==0) return E;
mat tmp=fast(mul(a,a,c),b>>1,c);
if(b%2==1) return mul(tmp,a,c);
return tmp;
}
mat calc(mat a,LL st,LL ed,LL c){
mat ret,tmp;
//printf("%I64d %I64d %d\n",st,ed,clock()-st);
if(st==ed) { //printf("%I64d %I64d %d\n",st,ed,clock()-st);
return fast(a,st,c);}
LL len=ed-st+1;
if(len%2==0){
ret=calc(a,st,st+len/2-1,c);
tmp=fast(a,len/2,c);
ret=add(ret,mul(tmp,ret,c),c);
}else{
ret=calc(a,st,ed-1,c);
tmp=fast(a,ed,c);
//ret=add(ret,mul(tmp,ret,c),c);
ret=add(ret,tmp,c);
} //printf("%I64d %I64d %d\n",st,ed,clock()-st);
return ret;
}
LL in(){
LL ret(0);char ch;
while(ch=getchar(),ch>'9'||ch<'0');
ret=ch-'0';
while(ch=getchar(),ch<='9'&&ch>='0') ret=ret*10+ch-'0';
return ret;
}
int main(){
st=clock();
//freopen("d:\\in.in","r",stdin);
//freopen("d:\\out.txt","w",stdout);
//mat d;
//for(int i=0;i<4;i++) for(int j=0;j<4;j++) d.M[i][j]=!((i&1)^(j&1));
//d.M[2][2]=5,d.M[2][3]=3,d.M[3][2]=3,d.M[3][3]=2;
//mat A;
//printf("%d\n",sizeof(A));
//calc(A4,0,,mod).write();
int test(0);
LL L,R;
for(scanf("%d",&test);test--;){
scanf("%I64d%I64d",&L,&R);
//L=in();R=in();
mat ans=calc(A4,L-1,R-1,mod);
ans=mul(A2,ans,mod);
//mat ans=fast(d,R-2,mod);
//printf("%I64d\n",(ans.M[0][0]+ans.M[0][2]*5+ans.M[0][3]*3)%mod);
printf("%I64d\n",ans.M[0][0]);
}
printf("%d\n",clock()-st);
//while(1);
return 0;
}