#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=j; i<=k; ++i)
#define ROF(i,j,k) for(int i=j; i>=k; --i)
using ll = long long;
const int maxn = 65;
const int mod = 1000000007;
inline void inc (int&a, int b) { (a += b) >= mod ? a -= mod : a; }
int k, f[maxn][2][2][2][2], bn[maxn], bm[maxn];
int dfs (int now, bool ok, bool dif, bool fn, bool fm) {
  if(!now) return ok;
  int&res = f[now][ok][dif][fn][fm];
  if(res != -1) return res; res = 0;
  int upi = fn ? k - 1 : bn[now], upj = fm ? k - 1 : bm[now];
  FOR(i,0,upi) for(int j=0; (j<=i||dif)&&j<=upj; ++j)
    inc (res, dfs (now-1, i<j|ok, i!=j|dif, i<upi|fn, j<upj|fm));
  return res;
}
int main (void) {
  int t;
  scanf("%d %d", &t, &k);
  while(t--) {
    memset(f, -1, sizeof(f));
    memset(bn, 0, sizeof(bn));
    memset(bm, 0, sizeof(bm));
    ll n, m;
    scanf("%lld %lld", &n, &m);
    int lenn = 0, lenm = 0;
    while(n) {
      bn[++ lenn] = n % k;
      n /= k;
    }
    while(m) {
      bm[++ lenm] = m % k;
      m /= k;
    }
    printf("%d\n", dfs (std::max(lenn, lenm), 0, 0, 0, 0));
  }
  return 0;
}