#include<stdio.h>

 const int mod=1e9+;

 #define LL __int64

 LL p[][];

 LL q[][];

 LL bb(LL a,LL b,LL c,LL d)

 {

     return (a*c%mod+b*d%mod)%mod;

 }

 LL aa(int n)

 {

     LL a,b,c,d;

     LL x,y;

     p[][]=;

     p[][]=;

     p[][]=;

     p[][]=;

     q[][]=;

     q[][]=;

     while(n)

     {

         a=p[][];b=p[][];c=p[][];d=p[][];

         x=q[][];y=q[][];

         if(n&){

             q[][]=bb(x,y,a,c);

             q[][]=bb(x,y,b,d);

         }

         p[][]=bb(a,b,a,c);

         p[][]=bb(a,b,b,d);

         p[][]=bb(c,d,a,c);

         p[][]=bb(c,d,b,d);

         n>>=;

     }

     return (q[][]%mod);

 }

 int main()

 {

     int T,n,m;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&m);

         if(n<m)

             printf("0\n");

         else if(n-m==)

             printf("1\n");

         else if(n-m==)

             printf("2\n");

         else

             printf("%I64d\n",aa(n-m-));

     }

     return ;

 }