#include <bits/stdc++.h>
using namespace std;
const int MOD(1000000007);
void Get_Val(int &Ret) {
  Ret = 0;
  char ch;
  while (ch = getchar(), ch > '9' || ch < '0')
    ;
  do {
    (Ret *= 10) += ch - '0';
  } while (ch = getchar(), ch >= '0' && ch <= '9');
}
inline int Mult(const int &a, const int &b) { return (a * 1LL) * b % MOD; }
int gcd(const int &a, const int &b) { return b == 0 ? a : gcd(b, a % b); }
constexpr int Add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
constexpr int Sub(int a, int b) { return a - b < 0 ? a - b + MOD : a - b; }
void exgcd(const int &a, const int &b, int &x, int &y) {
  if (b == 0)
    x = 1, y = 0;
  else
    exgcd(b, a % b, y, x), y -= x * (a / b);
}
inline int inverse(const int &a) {
  int invx, invy;
  exgcd(a, MOD, invx, invy);
  return (invx % MOD + MOD) % MOD;
}
int power(int a, int n) {
  int Ret(1);
  while (n) {
    if (n & 1) Ret = Mult(Ret, a);
    a = Mult(a, a), n >>= 1;
  }
  return Ret;
}
struct fun {
  fun(const int &_k = 0, const int &_b = 0) : k(_k), b(_b) {}
  int k, b;
  inline int get(const int &x) const { return Add(Mult(k, x), b); }
  inline fun get(const fun &v) const {
    return fun(Mult(k, v.k), Add(Mult(k, v.b), b));
  }
  inline fun operator+(const int &v) const { return fun(k, Add(b, v)); }
  inline fun operator+(const fun &v) const {
    return fun(Add(k, v.k), Add(b, v.b));
  }
  inline fun operator*(const int &v) const {
    return fun(Mult(k, v), Mult(b, v));
  }
};
inline fun inverse(const fun &a) {
  return fun(inverse(a.k), Sub(0, Mult(a.b, inverse(a.k))));
}
int P;
inline int Sum1(const int &n) { return Mult(Mult(Add(1, n), n), inverse(2)); }
inline int Sum2(const int &a, const int &n) {
  if (a == 1)
    return n + 1;
  else
    return Mult(Sub(power(a, n + 1), 1), inverse(a - 1));
}
inline int Sum3(const int a, const int &n) { return Sub(Sum2(a, n), 1); }
fun F(fun a, int n) {
  if (n < 0) a = inverse(a), n = -n;
  if (n == 0) return fun(1, 0);
  return fun(power(a.k, n), Mult(Sum2(a.k, n - 1), a.b));
}
fun G(fun a, int n) {
  if (n < 0) a = inverse(a), n = -n;
  if (n == 0) return fun(0, 0);
  if (a.k == 1)
    return fun(n, Mult(a.b, Sum1(n)));
  else
    return fun(Sum3(a.k, n),
               Mult(a.b, Mult(Sub(Sum3(a.k, n), n), inverse(Sub(a.k, 1)))));
}
int solve(const int &N, const int &K, const fun &S1, const fun &S2,
          const fun &A, const fun &B) {
  if (N == 1) {
    int E0 = Mult(B.b, inverse(Sub(1, B.k)));
    return S1.get(E0);
  }
  fun _S1, _S2, _A, _B;
  _S1 = S1 + G(A, (N - 1) / K) * S2.k + Mult(S2.b, (N - 1) / K);
  _S2 = S1 + G(A, (N - 1) / K - 1) * S2.k + Mult(S2.b, (N - 1) / K - 1);
  _A = (F(A, -((N - 1) / K - 1))).get(F(B, -1));
  _B = (F(A, -((N - 1) / K))).get(F(B, -1));
  return solve(K, (N - 1) % K + 1, _S1, _S2, _A, _B);
}
int main() {
  int T, N, K, D;
  Get_Val(T);
  while (T--)
    Get_Val(N), Get_Val(K),
        P = inverse(2), D = gcd(N, K), N /= D, K /= D,
        printf("%d\n", Mult(inverse(N), solve(N, K, fun(1, 0), fun(1, 0),
                                              fun(1, 1), fun(Sub(1, P), 1))));
  return 0;
}

### Prompt

Please formulate a CPP solution to the following problem:

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;
const int MOD(1000000007);
void Get_Val(int &Ret) {
  Ret = 0;
  char ch;
  while (ch = getchar(), ch > '9' || ch < '0')
    ;
  do {
    (Ret *= 10) += ch - '0';
  } while (ch = getchar(), ch >= '0' && ch <= '9');
}
inline int Mult(const int &a, const int &b) { return (a * 1LL) * b % MOD; }
int gcd(const int &a, const int &b) { return b == 0 ? a : gcd(b, a % b); }
constexpr int Add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
constexpr int Sub(int a, int b) { return a - b < 0 ? a - b + MOD : a - b; }
void exgcd(const int &a, const int &b, int &x, int &y) {
  if (b == 0)
    x = 1, y = 0;
  else
    exgcd(b, a % b, y, x), y -= x * (a / b);
}
inline int inverse(const int &a) {
  int invx, invy;
  exgcd(a, MOD, invx, invy);
  return (invx % MOD + MOD) % MOD;
}
int power(int a, int n) {
  int Ret(1);
  while (n) {
    if (n & 1) Ret = Mult(Ret, a);
    a = Mult(a, a), n >>= 1;
  }
  return Ret;
}
struct fun {
  fun(const int &_k = 0, const int &_b = 0) : k(_k), b(_b) {}
  int k, b;
  inline int get(const int &x) const { return Add(Mult(k, x), b); }
  inline fun get(const fun &v) const {
    return fun(Mult(k, v.k), Add(Mult(k, v.b), b));
  }
  inline fun operator+(const int &v) const { return fun(k, Add(b, v)); }
  inline fun operator+(const fun &v) const {
    return fun(Add(k, v.k), Add(b, v.b));
  }
  inline fun operator*(const int &v) const {
    return fun(Mult(k, v), Mult(b, v));
  }
};
inline fun inverse(const fun &a) {
  return fun(inverse(a.k), Sub(0, Mult(a.b, inverse(a.k))));
}
int P;
inline int Sum1(const int &n) { return Mult(Mult(Add(1, n), n), inverse(2)); }
inline int Sum2(const int &a, const int &n) {
  if (a == 1)
    return n + 1;
  else
    return Mult(Sub(power(a, n + 1), 1), inverse(a - 1));
}
inline int Sum3(const int a, const int &n) { return Sub(Sum2(a, n), 1); }
fun F(fun a, int n) {
  if (n < 0) a = inverse(a), n = -n;
  if (n == 0) return fun(1, 0);
  return fun(power(a.k, n), Mult(Sum2(a.k, n - 1), a.b));
}
fun G(fun a, int n) {
  if (n < 0) a = inverse(a), n = -n;
  if (n == 0) return fun(0, 0);
  if (a.k == 1)
    return fun(n, Mult(a.b, Sum1(n)));
  else
    return fun(Sum3(a.k, n),
               Mult(a.b, Mult(Sub(Sum3(a.k, n), n), inverse(Sub(a.k, 1)))));
}
int solve(const int &N, const int &K, const fun &S1, const fun &S2,
          const fun &A, const fun &B) {
  if (N == 1) {
    int E0 = Mult(B.b, inverse(Sub(1, B.k)));
    return S1.get(E0);
  }
  fun _S1, _S2, _A, _B;
  _S1 = S1 + G(A, (N - 1) / K) * S2.k + Mult(S2.b, (N - 1) / K);
  _S2 = S1 + G(A, (N - 1) / K - 1) * S2.k + Mult(S2.b, (N - 1) / K - 1);
  _A = (F(A, -((N - 1) / K - 1))).get(F(B, -1));
  _B = (F(A, -((N - 1) / K))).get(F(B, -1));
  return solve(K, (N - 1) % K + 1, _S1, _S2, _A, _B);
}
int main() {
  int T, N, K, D;
  Get_Val(T);
  while (T--)
    Get_Val(N), Get_Val(K),
        P = inverse(2), D = gcd(N, K), N /= D, K /= D,
        printf("%d\n", Mult(inverse(N), solve(N, K, fun(1, 0), fun(1, 0),
                                              fun(1, 1), fun(Sub(1, P), 1))));
  return 0;
}

```