#include <bits/stdc++.h>
using namespace std;
int n, k, T;
inline int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
inline int Pow(int x, int y) {
  int ans = 1, t = x;
  while (y > 0) {
    if (y & 1) ans = 1ll * ans * t % 1000000007;
    t = 1ll * t * t % 1000000007;
    y = y >> 1;
  }
  return ans;
}
inline int F(int q, int n) {
  if (n <= 0) return 0;
  if (q == 1) return n;
  return 1ll * (Pow(q, n) - 1) * Pow(q - 1, 1000000007 - 2) % 1000000007;
}
inline int G(int q, int n) {
  if (n <= 0) return 0;
  if (q == 1) return 1ll * n * (n + 1) / 2 % 1000000007;
  int v = Pow(q - 1, 1000000007 - 2);
  return (1ll * (Pow(q, n) - 1) * v % 1000000007 * q % 1000000007 - n +
          1000000007) %
         1000000007 * v % 1000000007;
}
inline int work(int n, int k, int a[], int b[], int s1[], int s2[]) {
  if (n == 1 && k == 0) {
    int X0 =
        1ll * a[0] * Pow(1000000007 + 1 - a[1], 1000000007 - 2) % 1000000007;
    return (1ll * s2[1] * X0 + s2[0]) % 1000000007;
  }
  int _a[2], _b[2], _s1[2], _s2[2], p = n / k;
  int X = 1ll * b[1] * Pow(a[1], p - 1) % 1000000007;
  int Y = (1ll * a[0] * b[1] % 1000000007 * F(a[1], p - 1) + b[0]) % 1000000007;
  _a[1] = Pow(X, 1000000007 - 2);
  _a[0] = (-1ll * Y * _a[1] % 1000000007 + 1000000007) % 1000000007;
  X = 1ll * b[1] * Pow(a[1], p) % 1000000007;
  Y = (1ll * a[0] * b[1] % 1000000007 * F(a[1], p) + b[0]) % 1000000007;
  _b[1] = Pow(X, 1000000007 - 2),
  _b[0] = (-1ll * Y * _b[1] % 1000000007 + 1000000007) % 1000000007;
  _s1[1] = (s1[1] + 1ll * s2[1] * a[1] % 1000000007 * F(a[1], p)) % 1000000007;
  _s2[1] =
      (s1[1] + 1ll * s2[1] * a[1] % 1000000007 * F(a[1], p - 1)) % 1000000007;
  _s1[0] =
      (s1[0] + 1ll * s2[1] * a[0] % 1000000007 * G(a[1], p) + 1ll * p * s2[0]) %
      1000000007;
  _s2[0] = (s1[0] + 1ll * s2[1] * a[0] % 1000000007 * G(a[1], p - 1) +
            1ll * (p - 1) * s2[0]) %
           1000000007;
  return work(k, n % k, _a, _b, _s1, _s2);
}
int main() {
  cin >> T;
  while (T--) {
    cin >> n >> k;
    int d = gcd(n, k);
    n /= d;
    k /= d;
    int a[2] = {1, 1}, b[2] = {1, 1000000007 + 1 >> 1}, s1[2] = {0, 1},
        s2[2] = {0, 1};
    printf("%d\n", 1ll * work(n, k, a, b, s1, s2) * Pow(n, 1000000007 - 2) %
                       1000000007);
  }
  return 0;
}
