#include <bits/stdc++.h>
using namespace std;
int fexp(int x, int t) {
  if (!t) return 1;
  int tmp = fexp(x, t >> 1);
  tmp = 1ll * tmp * tmp % 1000000007;
  return (t & 1) ? 1ll * tmp * x % 1000000007 : tmp;
}
const int hf = (1000000007 + 1) / 2;
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
int calc(int a, int q) {
  if (q <= 0) return 0;
  if (a == 1) return q;
  return 1ll * (fexp(a, q) - 1) * fexp(a - 1, 1000000007 - 2) % 1000000007;
}
int Calc(int a, int q) {
  if (q <= 0) return 0;
  if (a == 1) return 1ll * q * (q + 1) / 2 % 1000000007;
  int t = fexp(a - 1, 1000000007 - 2);
  return (1ll * (fexp(a, q) - 1) * t % 1000000007 * a - q + 1000000007) %
         1000000007 * t % 1000000007;
}
int solve(int n, int k, int a1, int b1, int a2, int b2, int c1, int c2,
          int c0) {
  if (n == k) {
    int x = 1ll * b2 * fexp(1000000007 + 1 - a2, 1000000007 - 2) % 1000000007;
    return (1ll * c1 * x + c0) % 1000000007;
  }
  int q = (n - 1) / k, r = n - q * k, A1, B1, A2, B2, C1, C2, C0, a, b;
  a = 1ll * a2 * fexp(a1, q - 1) % 1000000007,
  b = (1ll * a2 * b1 % 1000000007 * calc(a1, q - 1) + b2) % 1000000007;
  A1 = fexp(a, 1000000007 - 2);
  B1 = (1000000007 - 1ll * b * A1 % 1000000007) % 1000000007;
  a = 1ll * a2 * fexp(a1, q) % 1000000007,
  b = (1ll * a2 * b1 % 1000000007 * calc(a1, q) + b2) % 1000000007;
  A2 = fexp(a, 1000000007 - 2);
  B2 = (1000000007 - 1ll * b * A2 % 1000000007) % 1000000007;
  C1 = (c1 + 1ll * c2 * a1 % 1000000007 * calc(a1, q)) % 1000000007;
  C2 = (c1 + 1ll * c2 * a1 % 1000000007 * calc(a1, q - 1)) % 1000000007;
  C0 = (c0 + 1ll * c2 * b1 % 1000000007 *
                 (1ll * r * calc(a1, q) % 1000000007 +
                  1ll * k * Calc(a1, q - 1) % 1000000007)) %
       1000000007;
  return solve(k, r, A1, B1, A2, B2, C1, C2, C0);
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, k, d;
    scanf("%d%d", &n, &k);
    d = gcd(n, k);
    n /= d, k /= d;
    printf("%d\n", 1ll * solve(n, k, 1, 1, hf, 1, 1, 1, 0) *
                       fexp(n, 1000000007 - 2) % 1000000007);
  }
  return 0;
}
