#include <bits/stdc++.h>

 using namespace std;

 const int MAXN = 1e5 + ;

 typedef __int64 LL;

 LL mod = 1e9 + ;

 LL dp[MAXN] , ans[MAXN];

 int main()

 {

     int n , k , a , b;

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

     dp[] = ;

     ans[] = ;

     for(int i =  ; i <= 1e5 ; ++i) {

         if(i >= k)

             dp[i] = (dp[i - k] + dp[i - ]) % mod;

         else

             dp[i] = ;

         ans[i] = (ans[i - ] + dp[i]) % mod;

     }

     while(n--) {

         scanf("%d %d" , &a , &b);

         printf("%lld\n" , (ans[b] - ans[a - ] + mod) % mod);

     }

     return ;

 }