#include <bits/stdc++.h>
using namespace std;
const int RLEN = 1 << 20 | 1;
inline char gc() {
  static char ibuf[RLEN], *ib, *ob;
  (ob == ib) && (ob = (ib = ibuf) + fread(ibuf, 1, RLEN, stdin));
  return (ob == ib) ? EOF : *ib++;
}
inline int read() {
  char ch = getchar();
  int res = 0, f = 1;
  while (!isdigit(ch)) f ^= ch == '-', ch = getchar();
  while (isdigit(ch)) res = (res + (res << 2) << 1) + (ch ^ 48), ch = getchar();
  return f ? res : -res;
}
const int mod = 1e9 + 7;
inline int add(int a, int b) { return (a += b) >= mod ? a - mod : a; }
inline void Add(int &a, int b) { (a += b) >= mod ? a -= mod : 0; }
inline int dec(int a, int b) { return (a -= b) < 0 ? a + mod : a; }
inline void Dec(int &a, int b) { (a -= b) < 0 ? a += mod : 0; }
inline int mul(int a, int b) { return 1ll * a * b % mod; }
inline void Mul(int &a, int b) { a = 1ll * a * b % mod; }
inline int ksm(int a, int b, int res = 1) {
  for (; b; b >>= 1, Mul(a, a)) (b & 1) && (Mul(res, a), 1);
  return res;
}
inline int Inv(int x) { return ksm(x, mod - 2); }
inline void chemx(int &a, int b) { a < b ? a = b : 0; }
inline void chemn(int &a, int b) { a > b ? a = b : 0; }
struct node {
  int x, y;
  node(int _x = 0, int _y = 0) : x(_x), y(_y) {}
  friend inline node operator+(const node &a, const node &b) {
    return node(add(a.x, b.x), add(a.y, b.y));
  }
  friend inline node operator+(const node &a, const int &b) {
    return node(a.x, add(a.y, b));
  }
  friend inline node operator-(const node &a, const node &b) {
    return node(dec(a.x, b.x), dec(a.y, b.y));
  }
  friend inline node operator-(const node &a, const int &b) {
    return node(a.x, dec(a.y, b));
  }
  friend inline node operator*(const node &a, const node &b) {
    return node(mul(a.x, b.x), add(mul(a.y, b.x), b.y));
  }
  int calc(int a) { return add(mul(a, x), y); }
};
inline node Inv(node x) {
  int t = Inv(x.x);
  x.x = t, x.y = dec(0, mul(x.y, t));
  return x;
}
inline node ksm(node a, int b) {
  node res(1, 0);
  for (; b; b >>= 1, a = a * a)
    if (b & 1) res = res * a;
  return res;
}
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline node S(node a, int b) {
  if (!b) return node(0, 0);
  if (a.x == 1) return node(b, 1ll * b * (b + 1) / 2 % mod * a.y % mod);
  node x = ksm(a, b + 1) - a, p;
  p.x = mul(x.x, Inv(a.x - 1));
  p.y = mul(mul(dec(p.x, b), Inv(dec(a.x, 1))), a.y);
  return p;
}
inline int solve(int n, int k, node A, node B, node f1, node f2) {
  if (k == 0) {
    return f2.calc(mul(dec(0, A.y), Inv(dec(A.x, 1))));
  }
  int k1 = n % k, t = n / k;
  node F1 = f1 + S(A, t) * f2;
  node F2 = f1 + S(A, t - 1) * f2;
  node a = Inv(B) * ksm(Inv(A), t - 1), b = Inv(B) * ksm(Inv(A), t);
  return add(solve(k, k1, a, b, node(F1.x, 0), node(F2.x, 0)),
             add(mul(k1, F1.y), mul(k - k1, F2.y)));
}
int n, k, p;
node f1, f2, A, B;
int main() {
  int T = read();
  while (T--) {
    n = read(), k = read(), p = Inv(2);
    int g = gcd(n, k);
    n /= g, k /= g;
    f1 = node(1, 0), f2 = node(1, 0), A = node(1, 1), B = node(dec(1, p), 1);
    cout << mul(solve(n, k, A, B, f1, f2), Inv(n)) << '\n';
  }
}
