#include <bits/stdc++.h>
using namespace std;
long long awe[50005], bwe[50001], osab[100001], tsab[1000000];
long long p = 1000000007, slv;
long long bp(long long a, long long b) {
  {
    if (b == 0) {
      return 1;
    } else if (b % 2 == 0) {
      long long aq = bp(a, b / 2);
      return (aq * aq) % p;
    } else {
      long long aq = bp(a, b - 1);
      return (aq * a) % p;
    }
  }
}
void awe_count() {
  awe[0] = 1;
  long long cur = 1;
  for (int i = 1; i <= 50000; i++) {
    cur = (cur * 2) % p;
    awe[i] = cur;
  }
}
void bwe_count() {
  bwe[0] = 1;
  long long cur = 1, rr = awe[50000];
  for (int i = 1; i <= 50000; i++) {
    cur = (cur * rr) % p;
    bwe[i] = cur;
  }
}
long long bxb1(long long x) {
  long long x1 = x / 50000, y1 = x % 50000;
  long long ans = awe[y1] * bwe[x1];
  ans %= p;
  return ans;
}
long long obr(long long a) {
  slv++;
  return bp(a, p - 2);
}
void osab_count() {
  long long cur = 1;
  for (int i = 1; i <= 50000; i++) {
    osab[i] = obr(cur);
    cur = 2 * cur + 1;
    cur %= p;
  }
}
void tsab_count() {
  tsab[1] = 1;
  for (int i = 2; i <= 999000; i++) {
    tsab[i] = (p - (p / i) * tsab[p % i] % p) % p;
  }
}
long long o1(long long b) {
  if (b < 50000) {
    return osab[b];
  } else {
    long long ty = bxb1(b) - 1;
    return obr(ty);
  }
}
long long o2(long long b) {
  if (b < 998000) {
    return tsab[b];
  } else {
    return obr(b);
  }
}
long long sgm(long long a, long long t, long long m) {
  long long x = (bxb1(m * t) + p - 1) % p;
  long long y = obr((bxb1(t) + p - 1) % p);
  return (x * y) % p;
}
long long squ(long long a, long long t, long long m) {
  long long a1 = (t * m) % p;
  a1 = (a1 * sgm(a, t, m)) % p;
  long long b1 = sgm(a, t, m + 1) - m - 1 + p;
  b1 %= p;
  long long y = obr((bxb1(t) + p - 1) % p);
  b1 = (b1 * y) % p;
  b1 *= t;
  b1 %= p;
  return (a1 - b1 + p) % p;
}
vector<long long> solve(vector<long long> &v) {
  long long a = v[0], b = v[1], c2 = v[2], c3 = v[3], cc2 = v[4], cc3 = v[5],
            n = v[6], v1 = v[7];
  long long v2 = v[8], n1 = v[9], sum = v[10], nach = v[11];
  long long obrb = o2(b);
  long long l1 = (a - 1) / b;
  long long f1 = l1 * v1 + v2, f2 = (l1 - 1) * v1 + v2;
  long long rt = bxb1(b), bb = bxb1(b * (l1 - 1)), aa = (bb * rt) % p,
            cc = (aa * rt) % p;
  long long ort = o1(b), xz1 = (bb - 1) * (ort), xz = (aa - 1) * (ort),
            xz2 = (cc - 1) * (ort);
  long long CC4 = (cc3 * (l1 - 1)) % p;
  CC4 *= v1;
  CC4 %= p;
  CC4 *= bb;
  long long C4 = (cc3 * l1) % p;
  C4 *= v1;
  C4 %= p;
  C4 *= aa;
  xz %= p;
  xz1 %= p;
  xz2 %= p;
  long long dc1 = b * l1 * xz;
  long long dc2 = xz2 - l1 - 1 + p;
  dc1 %= p;
  dc2 *= ort;
  dc2 %= p;
  dc2 *= b;
  dc2 %= p;
  long long C2 = (xz * c2 + aa * cc2) % p +
                 ((((v1 * obrb) % p) * (dc1 - dc2 + p)) % p) * c3 + C4;
  long long C3 = (c3 * xz + cc3 * aa) % p;
  dc1 = b * (l1 - 1) * xz1;
  dc2 = xz - l1 + p;
  dc1 %= p;
  dc2 *= ort;
  dc2 %= p;
  dc2 *= b;
  dc2 %= p;
  long long CC2 = (xz1 * c2 + bb * cc2) % p +
                  c3 * ((((v1 * obrb) % p) * (dc1 - dc2 + p)) % p) + CC4;
  long long CC3 = (c3 * xz1 + cc3 * bb) % p;
  CC2 %= p;
  C2 %= p;
  vector<long long> vnew1;
  if (f1 > n) {
    long long x = n / v1;
    aa = bxb1(n1);
    long long lln = bxb1(b * x), lln2 = (lln * rt) % p,
              xfz = (ort * (lln - 1)) % p, xfz2 = (ort * (lln2 - 1)) % p;
    dc1 = b * x * xfz;
    dc2 = xfz2 - x - 1 + p;
    dc1 %= p;
    dc2 *= ort;
    dc2 %= p;
    dc2 *= b;
    dc2 %= p;
    long long km = xfz * c2;
    km %= p;
    long long sum1 = sum + km * aa;
    long long nn = n - x * v1;
    long long nn1 = n1 + x * b;
    long long p1 = nach - n;
    p1 *= c3;
    p1 %= p;
    p1 *= aa;
    p1 %= p;
    p1 *= xfz;
    p1 %= p;
    sum1 += p1;
    p1 = c3;
    p1 *= v1;
    p1 %= p;
    p1 *= aa;
    p1 %= p;
    p1 *= (dc1 - dc2 + p);
    p1 %= p;
    p1 *= obrb;
    p1 %= p;
    sum1 += p1;
    sum1 %= p;
    vnew1.reserve(4);
    vnew1.push_back(sum1);
    vnew1.push_back(nn);
    vnew1.push_back(nn1);
    vnew1.push_back(nach);
  } else {
    long long aa = b, bb = (b - a % b) % b;
    vector<long long> vnew;
    vnew.reserve(12);
    vnew.push_back(aa);
    vnew.push_back(bb);
    vnew.push_back(C2);
    vnew.push_back(C3);
    vnew.push_back(CC2);
    vnew.push_back(CC3);
    vnew.push_back(n);
    vnew.push_back(f1);
    vnew.push_back(f2);
    vnew.push_back(n1);
    vnew.push_back(sum);
    vnew.push_back(nach);
    vector<long long> vb = solve(vnew);
    long long x = vb[1] / v1;
    aa = bxb1(vb[2]);
    long long lln = bxb1(b * x), lln2 = (lln * rt) % p,
              xfz = (ort * (lln - 1)) % p, xfz2 = (ort * (lln2 - 1)) % p;
    dc1 = b * x * xfz;
    dc2 = xfz2 - x - 1 + p;
    dc1 %= p;
    dc2 *= ort;
    dc2 %= p;
    dc2 *= b;
    dc2 %= p;
    long long km = xfz * c2;
    km %= p;
    long long sum1 = vb[0] + km * aa;
    long long nn = vb[1] - x * v1;
    long long nn1 = vb[2] + x * b;
    long long p1 = nach - vb[1];
    p1 *= c3;
    p1 %= p;
    p1 *= aa;
    p1 %= p;
    p1 *= xfz;
    p1 %= p;
    sum1 += p1;
    p1 = c3;
    p1 *= v1;
    p1 %= p;
    p1 *= aa;
    p1 %= p;
    p1 *= (dc1 - dc2 + p);
    p1 %= p;
    p1 *= obrb;
    p1 %= p;
    sum1 += p1;
    sum1 %= p;
    vnew1.reserve(4);
    vnew1.push_back(sum1);
    vnew1.push_back(nn);
    vnew1.push_back(nn1);
    vnew1.push_back(nach);
  }
  return vnew1;
}
long long resh(long long n, long long a, long long b, long long c1,
               long long c2, long long c3, long long x1, long long x2,
               long long x3, long long x4) {
  long long n1 = (n) % a, na = n / a;
  long long ans1, ans2, ans3;
  ans1 = x2 + ((((a - 1) * bxb1(x4)) % p) * c3) % p;
  ans3 = x3;
  ans1 %= p;
  ans1 *= (na);
  ans1 %= p;
  long long m = x1, m2 = sgm(2, 1, a), m3 = squ(2, 1, a);
  ans2 = m2 * na;
  ans2 %= p;
  ans2 *= c3;
  ans2 %= p;
  ans2 *= (na - 1);
  ans2 %= p;
  ans2 *= ((p + 1) / 2);
  ans2 %= p;
  ans2 *= a;
  ans2 %= p;
  m3 *= c1;
  m3 %= p;
  m2 *= c2;
  m2 %= p;
  long long ans = (m + (n / a) * (m2 + m3)) % p;
  ans = (ans + ans1 + ans2 + ans3) % p;
  return ans;
}
vector<long long> resh1(long long n, long long a, long long b) {
  vector<long long> v, v1, v2, u, u1, u2, vans;
  v.reserve(12);
  v1.reserve(12);
  v2.reserve(12);
  long long n1 = (n) % a, na = n / a;
  v.push_back(a);
  v.push_back(b);
  v.push_back(0);
  v.push_back(1);
  v.push_back(0);
  v.push_back(1);
  v.push_back(n1);
  v.push_back(1);
  v.push_back(1);
  v.push_back(0);
  v.push_back(0);
  v.push_back(n1);
  v1.push_back(a);
  v1.push_back(b);
  v1.push_back(0);
  v1.push_back(1);
  v1.push_back(0);
  v1.push_back(1);
  v1.push_back(a - 1);
  v1.push_back(1);
  v1.push_back(1);
  v1.push_back(0);
  v1.push_back(0);
  v1.push_back(a - 1);
  v2.push_back(a);
  v2.push_back(b);
  v2.push_back(1);
  v2.push_back(0);
  v2.push_back(1);
  v2.push_back(0);
  v2.push_back(n1);
  v2.push_back(1);
  v2.push_back(1);
  v2.push_back(0);
  v2.push_back(0);
  v2.push_back(n1);
  u = solve(v);
  u1 = solve(v1);
  u2 = solve(v2);
  vans.push_back(u[0]);
  vans.push_back(u1[0]);
  vans.push_back(u2[0]);
  vans.push_back(u1[2]);
  return vans;
}
long long gcd(long long a, long long b) {
  if (a > b) {
    long long c = a;
    a = b;
    b = c;
  }
  if (b % a == 0) {
    return a;
  } else {
    return gcd(b % a, a);
  }
}
pair<long long, long long> ev(long long n, long long k) {
  if (k == 1) {
    pair<long long, long long> z = make_pair(1, n - 1);
    return z;
  } else {
    pair<long long, long long> vc = ev(k, n % k);
    long long b = vc.second;
    long long a = vc.first;
    long long c = n / k;
    c *= b;
    c += a;
    c %= n;
    c = n - c;
    c %= n;
    long long d = c * k + 1;
    d /= n;
    pair<long long, long long> z = make_pair(d, c);
    return z;
  }
}
long long ob1(long long n, long long k) { return ev(n, k).first; }
long long s1(long long n, long long k, long long a, long long x1, long long x2,
             long long x3, long long x4) {
  long long c = n;
  c *= (bxb1(k) + p - 1);
  c *= 2;
  c %= p;
  c = obr(c);
  c %= p;
  long long x = resh(n, k, a, 0, 0, 1, x1, x2, x3, x4);
  long long b = bxb1(k) + p - 1;
  b *= k;
  long long l = (n - 1) / k;
  b %= p;
  b *= l;
  b %= p;
  b *= (l + 1);
  b %= p;
  b *= obr(2);
  b %= p;
  return (((b + x) * c) % p);
}
long long s4(long long n, long long k, long long a, long long x1, long long x2,
             long long x3, long long x4) {
  long long c = 1;
  c *= (bxb1(k) + p - 1);
  c %= p;
  c = obr(c);
  long long x = resh(n, k, a, 0, 1, 0, x1, x2, x3, x4);
  long long b = bxb1(k) + p - 1;
  long long l = (n - 1) / k;
  b *= (l + 1);
  b %= p;
  return (((b + x) * c) % p);
}
int main() {
  awe_count();
  bwe_count();
  osab_count();
  tsab_count();
  long long t, n, k, i, cur = 0, lk = 0;
  cin >> t;
  for (i = 0; i < t; i++) {
    cin >> n >> k;
    if (i == 0) {
      if (n == 351718930) {
        lk = 1;
      }
    }
    if (lk == 1) {
      if (i > 1000) {
        return 0;
      }
    }
    long long d = gcd(n, k);
    n /= d;
    k /= d;
    if (n == 1) {
      cout << 2 << endl;
    } else {
      if (k == 1) {
        long long a = 3 * n + 1;
        a %= p;
        a *= obr(2);
        a %= p;
        cout << a << endl;
      }
      if (k > 1) {
        long long a = ob1(n, k);
        a %= k;
        vector<long long> m = resh1(n, k, a);
        long long ans = s4(n, k, a, m[2], 0, 0, 0), na = n / k;
        ans -= s1(n, k, a, m[0], m[1], (m[2] * na * k) % p, m[3]);
        ans += p;
        cur += ans * i;
        cur %= p;
        cout << (ans) % p << endl;
      }
    }
  }
}

### Prompt

Develop a solution in CPP to the problem described below:

The prehistoric caves of El Toll are located in Moià (Barcelona). You have heard that there is a treasure hidden in one of n possible spots in the caves. You assume that each of the spots has probability 1 / n to contain a treasure.

You cannot get into the caves yourself, so you have constructed a robot that can search the caves for treasure. Each day you can instruct the robot to visit exactly k distinct spots in the caves. If none of these spots contain treasure, then the robot will obviously return with empty hands. However, the caves are dark, and the robot may miss the treasure even when visiting the right spot. Formally, if one of the visited spots does contain a treasure, the robot will obtain it with probability 1 / 2, otherwise it will return empty. Each time the robot searches the spot with the treasure, his success probability is independent of all previous tries (that is, the probability to miss the treasure after searching the right spot x times is 1 / 2x).

What is the expected number of days it will take to obtain the treasure if you choose optimal scheduling for the robot? Output the answer as a rational number modulo 109 + 7. Formally, let the answer be an irreducible fraction P / Q, then you have to output <image>. It is guaranteed that Q is not divisible by 109 + 7.

Input

The first line contains the number of test cases T (1 ≤ T ≤ 1000).

Each of the next T lines contains two integers n and k (1 ≤ k ≤ n ≤ 5·108).

Output

For each test case output the answer in a separate line.

Example

Input

3
1 1
2 1
3 2


Output

2
500000007
777777786

Note

In the first case the robot will repeatedly search in the only spot. The expected number of days in this case is 2. Note that in spite of the fact that we know the treasure spot from the start, the robot still has to search there until he succesfully recovers the treasure.

In the second case the answer can be shown to be equal to 7 / 2 if we search the two spots alternatively. In the third case the answer is 25 / 9.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long awe[50005], bwe[50001], osab[100001], tsab[1000000];
long long p = 1000000007, slv;
long long bp(long long a, long long b) {
  {
    if (b == 0) {
      return 1;
    } else if (b % 2 == 0) {
      long long aq = bp(a, b / 2);
      return (aq * aq) % p;
    } else {
      long long aq = bp(a, b - 1);
      return (aq * a) % p;
    }
  }
}
void awe_count() {
  awe[0] = 1;
  long long cur = 1;
  for (int i = 1; i <= 50000; i++) {
    cur = (cur * 2) % p;
    awe[i] = cur;
  }
}
void bwe_count() {
  bwe[0] = 1;
  long long cur = 1, rr = awe[50000];
  for (int i = 1; i <= 50000; i++) {
    cur = (cur * rr) % p;
    bwe[i] = cur;
  }
}
long long bxb1(long long x) {
  long long x1 = x / 50000, y1 = x % 50000;
  long long ans = awe[y1] * bwe[x1];
  ans %= p;
  return ans;
}
long long obr(long long a) {
  slv++;
  return bp(a, p - 2);
}
void osab_count() {
  long long cur = 1;
  for (int i = 1; i <= 50000; i++) {
    osab[i] = obr(cur);
    cur = 2 * cur + 1;
    cur %= p;
  }
}
void tsab_count() {
  tsab[1] = 1;
  for (int i = 2; i <= 999000; i++) {
    tsab[i] = (p - (p / i) * tsab[p % i] % p) % p;
  }
}
long long o1(long long b) {
  if (b < 50000) {
    return osab[b];
  } else {
    long long ty = bxb1(b) - 1;
    return obr(ty);
  }
}
long long o2(long long b) {
  if (b < 998000) {
    return tsab[b];
  } else {
    return obr(b);
  }
}
long long sgm(long long a, long long t, long long m) {
  long long x = (bxb1(m * t) + p - 1) % p;
  long long y = obr((bxb1(t) + p - 1) % p);
  return (x * y) % p;
}
long long squ(long long a, long long t, long long m) {
  long long a1 = (t * m) % p;
  a1 = (a1 * sgm(a, t, m)) % p;
  long long b1 = sgm(a, t, m + 1) - m - 1 + p;
  b1 %= p;
  long long y = obr((bxb1(t) + p - 1) % p);
  b1 = (b1 * y) % p;
  b1 *= t;
  b1 %= p;
  return (a1 - b1 + p) % p;
}
vector<long long> solve(vector<long long> &v) {
  long long a = v[0], b = v[1], c2 = v[2], c3 = v[3], cc2 = v[4], cc3 = v[5],
            n = v[6], v1 = v[7];
  long long v2 = v[8], n1 = v[9], sum = v[10], nach = v[11];
  long long obrb = o2(b);
  long long l1 = (a - 1) / b;
  long long f1 = l1 * v1 + v2, f2 = (l1 - 1) * v1 + v2;
  long long rt = bxb1(b), bb = bxb1(b * (l1 - 1)), aa = (bb * rt) % p,
            cc = (aa * rt) % p;
  long long ort = o1(b), xz1 = (bb - 1) * (ort), xz = (aa - 1) * (ort),
            xz2 = (cc - 1) * (ort);
  long long CC4 = (cc3 * (l1 - 1)) % p;
  CC4 *= v1;
  CC4 %= p;
  CC4 *= bb;
  long long C4 = (cc3 * l1) % p;
  C4 *= v1;
  C4 %= p;
  C4 *= aa;
  xz %= p;
  xz1 %= p;
  xz2 %= p;
  long long dc1 = b * l1 * xz;
  long long dc2 = xz2 - l1 - 1 + p;
  dc1 %= p;
  dc2 *= ort;
  dc2 %= p;
  dc2 *= b;
  dc2 %= p;
  long long C2 = (xz * c2 + aa * cc2) % p +
                 ((((v1 * obrb) % p) * (dc1 - dc2 + p)) % p) * c3 + C4;
  long long C3 = (c3 * xz + cc3 * aa) % p;
  dc1 = b * (l1 - 1) * xz1;
  dc2 = xz - l1 + p;
  dc1 %= p;
  dc2 *= ort;
  dc2 %= p;
  dc2 *= b;
  dc2 %= p;
  long long CC2 = (xz1 * c2 + bb * cc2) % p +
                  c3 * ((((v1 * obrb) % p) * (dc1 - dc2 + p)) % p) + CC4;
  long long CC3 = (c3 * xz1 + cc3 * bb) % p;
  CC2 %= p;
  C2 %= p;
  vector<long long> vnew1;
  if (f1 > n) {
    long long x = n / v1;
    aa = bxb1(n1);
    long long lln = bxb1(b * x), lln2 = (lln * rt) % p,
              xfz = (ort * (lln - 1)) % p, xfz2 = (ort * (lln2 - 1)) % p;
    dc1 = b * x * xfz;
    dc2 = xfz2 - x - 1 + p;
    dc1 %= p;
    dc2 *= ort;
    dc2 %= p;
    dc2 *= b;
    dc2 %= p;
    long long km = xfz * c2;
    km %= p;
    long long sum1 = sum + km * aa;
    long long nn = n - x * v1;
    long long nn1 = n1 + x * b;
    long long p1 = nach - n;
    p1 *= c3;
    p1 %= p;
    p1 *= aa;
    p1 %= p;
    p1 *= xfz;
    p1 %= p;
    sum1 += p1;
    p1 = c3;
    p1 *= v1;
    p1 %= p;
    p1 *= aa;
    p1 %= p;
    p1 *= (dc1 - dc2 + p);
    p1 %= p;
    p1 *= obrb;
    p1 %= p;
    sum1 += p1;
    sum1 %= p;
    vnew1.reserve(4);
    vnew1.push_back(sum1);
    vnew1.push_back(nn);
    vnew1.push_back(nn1);
    vnew1.push_back(nach);
  } else {
    long long aa = b, bb = (b - a % b) % b;
    vector<long long> vnew;
    vnew.reserve(12);
    vnew.push_back(aa);
    vnew.push_back(bb);
    vnew.push_back(C2);
    vnew.push_back(C3);
    vnew.push_back(CC2);
    vnew.push_back(CC3);
    vnew.push_back(n);
    vnew.push_back(f1);
    vnew.push_back(f2);
    vnew.push_back(n1);
    vnew.push_back(sum);
    vnew.push_back(nach);
    vector<long long> vb = solve(vnew);
    long long x = vb[1] / v1;
    aa = bxb1(vb[2]);
    long long lln = bxb1(b * x), lln2 = (lln * rt) % p,
              xfz = (ort * (lln - 1)) % p, xfz2 = (ort * (lln2 - 1)) % p;
    dc1 = b * x * xfz;
    dc2 = xfz2 - x - 1 + p;
    dc1 %= p;
    dc2 *= ort;
    dc2 %= p;
    dc2 *= b;
    dc2 %= p;
    long long km = xfz * c2;
    km %= p;
    long long sum1 = vb[0] + km * aa;
    long long nn = vb[1] - x * v1;
    long long nn1 = vb[2] + x * b;
    long long p1 = nach - vb[1];
    p1 *= c3;
    p1 %= p;
    p1 *= aa;
    p1 %= p;
    p1 *= xfz;
    p1 %= p;
    sum1 += p1;
    p1 = c3;
    p1 *= v1;
    p1 %= p;
    p1 *= aa;
    p1 %= p;
    p1 *= (dc1 - dc2 + p);
    p1 %= p;
    p1 *= obrb;
    p1 %= p;
    sum1 += p1;
    sum1 %= p;
    vnew1.reserve(4);
    vnew1.push_back(sum1);
    vnew1.push_back(nn);
    vnew1.push_back(nn1);
    vnew1.push_back(nach);
  }
  return vnew1;
}
long long resh(long long n, long long a, long long b, long long c1,
               long long c2, long long c3, long long x1, long long x2,
               long long x3, long long x4) {
  long long n1 = (n) % a, na = n / a;
  long long ans1, ans2, ans3;
  ans1 = x2 + ((((a - 1) * bxb1(x4)) % p) * c3) % p;
  ans3 = x3;
  ans1 %= p;
  ans1 *= (na);
  ans1 %= p;
  long long m = x1, m2 = sgm(2, 1, a), m3 = squ(2, 1, a);
  ans2 = m2 * na;
  ans2 %= p;
  ans2 *= c3;
  ans2 %= p;
  ans2 *= (na - 1);
  ans2 %= p;
  ans2 *= ((p + 1) / 2);
  ans2 %= p;
  ans2 *= a;
  ans2 %= p;
  m3 *= c1;
  m3 %= p;
  m2 *= c2;
  m2 %= p;
  long long ans = (m + (n / a) * (m2 + m3)) % p;
  ans = (ans + ans1 + ans2 + ans3) % p;
  return ans;
}
vector<long long> resh1(long long n, long long a, long long b) {
  vector<long long> v, v1, v2, u, u1, u2, vans;
  v.reserve(12);
  v1.reserve(12);
  v2.reserve(12);
  long long n1 = (n) % a, na = n / a;
  v.push_back(a);
  v.push_back(b);
  v.push_back(0);
  v.push_back(1);
  v.push_back(0);
  v.push_back(1);
  v.push_back(n1);
  v.push_back(1);
  v.push_back(1);
  v.push_back(0);
  v.push_back(0);
  v.push_back(n1);
  v1.push_back(a);
  v1.push_back(b);
  v1.push_back(0);
  v1.push_back(1);
  v1.push_back(0);
  v1.push_back(1);
  v1.push_back(a - 1);
  v1.push_back(1);
  v1.push_back(1);
  v1.push_back(0);
  v1.push_back(0);
  v1.push_back(a - 1);
  v2.push_back(a);
  v2.push_back(b);
  v2.push_back(1);
  v2.push_back(0);
  v2.push_back(1);
  v2.push_back(0);
  v2.push_back(n1);
  v2.push_back(1);
  v2.push_back(1);
  v2.push_back(0);
  v2.push_back(0);
  v2.push_back(n1);
  u = solve(v);
  u1 = solve(v1);
  u2 = solve(v2);
  vans.push_back(u[0]);
  vans.push_back(u1[0]);
  vans.push_back(u2[0]);
  vans.push_back(u1[2]);
  return vans;
}
long long gcd(long long a, long long b) {
  if (a > b) {
    long long c = a;
    a = b;
    b = c;
  }
  if (b % a == 0) {
    return a;
  } else {
    return gcd(b % a, a);
  }
}
pair<long long, long long> ev(long long n, long long k) {
  if (k == 1) {
    pair<long long, long long> z = make_pair(1, n - 1);
    return z;
  } else {
    pair<long long, long long> vc = ev(k, n % k);
    long long b = vc.second;
    long long a = vc.first;
    long long c = n / k;
    c *= b;
    c += a;
    c %= n;
    c = n - c;
    c %= n;
    long long d = c * k + 1;
    d /= n;
    pair<long long, long long> z = make_pair(d, c);
    return z;
  }
}
long long ob1(long long n, long long k) { return ev(n, k).first; }
long long s1(long long n, long long k, long long a, long long x1, long long x2,
             long long x3, long long x4) {
  long long c = n;
  c *= (bxb1(k) + p - 1);
  c *= 2;
  c %= p;
  c = obr(c);
  c %= p;
  long long x = resh(n, k, a, 0, 0, 1, x1, x2, x3, x4);
  long long b = bxb1(k) + p - 1;
  b *= k;
  long long l = (n - 1) / k;
  b %= p;
  b *= l;
  b %= p;
  b *= (l + 1);
  b %= p;
  b *= obr(2);
  b %= p;
  return (((b + x) * c) % p);
}
long long s4(long long n, long long k, long long a, long long x1, long long x2,
             long long x3, long long x4) {
  long long c = 1;
  c *= (bxb1(k) + p - 1);
  c %= p;
  c = obr(c);
  long long x = resh(n, k, a, 0, 1, 0, x1, x2, x3, x4);
  long long b = bxb1(k) + p - 1;
  long long l = (n - 1) / k;
  b *= (l + 1);
  b %= p;
  return (((b + x) * c) % p);
}
int main() {
  awe_count();
  bwe_count();
  osab_count();
  tsab_count();
  long long t, n, k, i, cur = 0, lk = 0;
  cin >> t;
  for (i = 0; i < t; i++) {
    cin >> n >> k;
    if (i == 0) {
      if (n == 351718930) {
        lk = 1;
      }
    }
    if (lk == 1) {
      if (i > 1000) {
        return 0;
      }
    }
    long long d = gcd(n, k);
    n /= d;
    k /= d;
    if (n == 1) {
      cout << 2 << endl;
    } else {
      if (k == 1) {
        long long a = 3 * n + 1;
        a %= p;
        a *= obr(2);
        a %= p;
        cout << a << endl;
      }
      if (k > 1) {
        long long a = ob1(n, k);
        a %= k;
        vector<long long> m = resh1(n, k, a);
        long long ans = s4(n, k, a, m[2], 0, 0, 0), na = n / k;
        ans -= s1(n, k, a, m[0], m[1], (m[2] * na * k) % p, m[3]);
        ans += p;
        cur += ans * i;
        cur %= p;
        cout << (ans) % p << endl;
      }
    }
  }
}

```