#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e5+;

const int mod=1e9+;

ll fac[maxn],inv[maxn],ans[maxn];

ll rev2,res;

int pos[maxn];

ll qpow(ll b,int n)

{

    ll res=;

    while(n)

    {

        if(n&) res=res*b%mod;

        b=b*b%mod;

        n>>=;

    }

    return res;

}

ll Comb(int n,int k)

{

    return fac[n]*inv[k]%mod*inv[n-k]%mod;

}

void pre()

{

    rev2=qpow(,mod-);

    fac[]=fac[]=;

    for(int i=; i<maxn; ++i) fac[i]=i*fac[i-]%mod;

    inv[maxn-]=qpow(fac[maxn-],mod-);

    for(int i=maxn-;i>=;i--) inv[i]=inv[i+]*(i+)%mod;

}

struct Query

{

    int L,R,id;

    bool operator <(const Query& p) const

    {

        if(pos[L]==pos[p.L]) return R<p.R;

        return L<p.L;

    }

} Q[maxn];

inline void addN(int posL,int posR)

{

    res=(*res%mod-Comb(posL-,posR)+mod)%mod;

}

inline void addM(int posL,int posR)

{

    res=(res+Comb(posL,posR))%mod;

}

inline void delN(int posL,int posR)

{

    res=(res+Comb(posL-,posR))%mod*rev2%mod;

}

inline void delM(int posL,int posR)

{

    res=(res-Comb(posL,posR)+mod)%mod;

}

int main()

{

    int T,curL,curR;

    int block=(int)sqrt(1.0*maxn);

    pre();

    scanf("%d",&T);

    for(int i=;i<=T;++i)

    {

        scanf("%d %d",&Q[i].L,&Q[i].R);

        pos[i]=i/block;

        Q[i].id=i;

    }

    sort(Q+,Q+T+);

    res=;

    curL=,curR=;

    for(int i=;i<=T;++i)

    {

        while(curL<Q[i].L) addN(++curL,curR);

        while(curR<Q[i].R) addM(curL,++curR);

        while(curL>Q[i].L) delN(curL--,curR);

        while(curR>Q[i].R) delM(curL,curR--);

        ans[Q[i].id] = res;

    }

    for(int i=;i<=T;++i) printf("%lld\n",ans[i]);

    return ;

}