#include <bits/stdc++.h>
using namespace std;
const int MOD(1000000007);
void Get_Val(int &Ret) {
  Ret = 0;
  char ch;
  while (ch = getchar(), ch > '9' || ch < '0')
    ;
  do {
    (Ret *= 10) += ch - '0';
  } while (ch = getchar(), ch >= '0' && ch <= '9');
}
inline int Mult(const int &a, const int &b) { return (a * 1LL) * b % MOD; }
int gcd(const int &a, const int &b) { return b == 0 ? a : gcd(b, a % b); }
constexpr int Add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
constexpr int Sub(int a, int b) { return a - b < 0 ? a - b + MOD : a - b; }
void exgcd(const int &a, const int &b, int &x, int &y) {
  if (b == 0)
    x = 1, y = 0;
  else
    exgcd(b, a % b, y, x), y -= x * (a / b);
}
inline int inverse(const int &a) {
  int invx, invy;
  exgcd(a, MOD, invx, invy);
  return (invx % MOD + MOD) % MOD;
}
int power(int a, int n) {
  int Ret(1);
  while (n) {
    if (n & 1) Ret = Mult(Ret, a);
    a = Mult(a, a), n >>= 1;
  }
  return Ret;
}
struct fun {
  fun(const int &_k = 0, const int &_b = 0) : k(_k), b(_b) {}
  int k, b;
  inline int get(const int &x) const { return Add(Mult(k, x), b); }
  inline fun get(const fun &v) const {
    return fun(Mult(k, v.k), Add(Mult(k, v.b), b));
  }
  inline fun operator+(const int &v) const { return fun(k, Add(b, v)); }
  inline fun operator+(const fun &v) const {
    return fun(Add(k, v.k), Add(b, v.b));
  }
  inline fun operator*(const int &v) const {
    return fun(Mult(k, v), Mult(b, v));
  }
};
inline fun inverse(const fun &a) {
  return fun(inverse(a.k), Sub(0, Mult(a.b, inverse(a.k))));
}
int P;
inline int Sum1(const int &n) { return Mult(Mult(Add(1, n), n), inverse(2)); }
inline int Sum2(const int &a, const int &n) {
  if (a == 1)
    return n + 1;
  else
    return Mult(Sub(power(a, n + 1), 1), inverse(a - 1));
}
inline int Sum3(const int a, const int &n) { return Sub(Sum2(a, n), 1); }
fun F(fun a, int n) {
  if (n < 0) a = inverse(a), n = -n;
  if (n == 0) return fun(1, 0);
  return fun(power(a.k, n), Mult(Sum2(a.k, n - 1), a.b));
}
fun G(fun a, int n) {
  if (n < 0) a = inverse(a), n = -n;
  if (n == 0) return fun(0, 0);
  if (a.k == 1)
    return fun(n, Mult(a.b, Sum1(n)));
  else
    return fun(Sum3(a.k, n),
               Mult(a.b, Mult(Sub(Sum3(a.k, n), n), inverse(Sub(a.k, 1)))));
}
int solve(const int &N, const int &K, const fun &S1, const fun &S2,
          const fun &A, const fun &B) {
  if (N == 1) {
    int E0 = Mult(B.b, inverse(Sub(1, B.k)));
    return S1.get(E0);
  }
  fun _S1, _S2, _A, _B;
  _S1 = S1 + G(A, (N - 1) / K) * S2.k + Mult(S2.b, (N - 1) / K);
  _S2 = S1 + G(A, (N - 1) / K - 1) * S2.k + Mult(S2.b, (N - 1) / K - 1);
  _A = (F(A, -((N - 1) / K - 1))).get(F(B, -1));
  _B = (F(A, -((N - 1) / K))).get(F(B, -1));
  return solve(K, (N - 1) % K + 1, _S1, _S2, _A, _B);
}
int main() {
  int T, N, K, D;
  Get_Val(T);
  while (T--)
    Get_Val(N), Get_Val(K),
        P = inverse(2), D = gcd(N, K), N /= D, K /= D,
        printf("%d\n", Mult(inverse(N), solve(N, K, fun(1, 0), fun(1, 0),
                                              fun(1, 1), fun(Sub(1, P), 1))));
  return 0;
}
