#include <bits/stdc++.h>
using namespace std;
const int Mo = 1e9 + 7, inv2 = 5e8 + 4;
int ty, n, k, p;
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
struct P {
  int k, b;
  P(int _k = 0, int _b = 0) {
    k = _k;
    b = _b;
  }
};
P operator*(P a, P b) {
  return P((long long)a.k * b.k % Mo, ((long long)b.k * a.b % Mo + b.b) % Mo);
}
P operator-(P a, P b) {
  return P((a.k - b.k + Mo) % Mo, (a.b - b.b + Mo) % Mo);
}
P operator+(P a, P b) { return P((a.k + b.k) % Mo, (a.b + b.b) % Mo); }
int calc(P a, int x) { return ((long long)a.k * x % Mo + a.b) % Mo; }
int pwr(int x, int y) {
  int z = 1;
  for (; y; y >>= 1, x = (long long)x * x % Mo)
    if (y & 1) z = (long long)z * x % Mo;
  return z;
}
P inv(P a) {
  int ia = pwr(a.k, Mo - 2);
  return P(ia, Mo - (long long)a.b * ia % Mo);
}
P pw(P x, int y) {
  P z = P(1, 0);
  for (; y; y >>= 1, x = x * x)
    if (y & 1) z = z * x;
  return z;
}
P ps(P x, int y) {
  if (!y) return P(0, 0);
  if (x.k == 1) return P(y, (long long)y * (y + 1) % Mo * inv2 % Mo * x.b % Mo);
  P a = pw(x, y + 1) - x, z;
  z.k = (long long)a.k * pwr(x.k - 1, Mo - 2) % Mo;
  z.b = (long long)(z.k - y + Mo) % Mo * pwr(x.k - 1, Mo - 2) % Mo * x.b % Mo;
  return z;
}
int solve(int n, int k, P A, P B, P S1, P S2) {
  if (!k)
    return ((long long)S2.k * A.b % Mo * pwr(Mo + 1 - A.k, Mo - 2) % Mo +
            S2.b) %
           Mo;
  P a, b, s1, s2;
  int k1 = n % k, t = n / k - 1;
  a = inv(B) * pw(inv(A), t);
  b = inv(B) * pw(inv(A), t + 1);
  s2 = S1 + ps(A, t) * S2;
  s1 = S1 + ps(A, t + 1) * S2;
  int sum =
      ((long long)(n % k) * s1.b % Mo + (long long)(k - n % k) * s2.b % Mo) %
      Mo;
  s1.b = s2.b = 0;
  return (sum + solve(k, n % k, a, b, s1, s2)) % Mo;
}
int main() {
  for (scanf("%d", &ty); ty; ty--) {
    scanf("%d%d", &n, &k);
    p = inv2;
    int g = gcd(n, k);
    n /= g;
    k /= g;
    printf("%d\n", (long long)solve(n, k, P(1, 1), P(p, 1), P(1, 0), P(1, 0)) *
                       pwr(n, Mo - 2) % Mo);
  }
  return 0;
}
