#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class t, class u>
void chmax(t& first, u second) {
  if (first < second) first = second;
}
template <class t, class u>
void chmin(t& first, u second) {
  if (second < first) first = second;
}
template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;
using pi = pair<ll, ll>;
using vi = vc<ll>;
template <class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
  return os << "{" << p.first << "," << p.second << "}";
}
template <class t>
ostream& operator<<(ostream& os, const vc<t>& v) {
  os << "{";
  for (auto e : v) os << e << ",";
  return os << "}";
}
using uint = unsigned;
using ull = unsigned long long;
template <class t, size_t n>
ostream& operator<<(ostream& os, const array<t, n>& first) {
  return os << vc<t>(first.begin(), first.end());
}
template <ll i, class T>
void print_tuple(ostream&, const T&) {}
template <ll i, class T, class H, class... Args>
void print_tuple(ostream& os, const T& t) {
  if (i) os << ",";
  os << get<i>(t);
  print_tuple<i + 1, T, Args...>(os, t);
}
template <class... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
  os << "{";
  print_tuple<0, tuple<Args...>, Args...>(os, t);
  return os << "}";
}
template <class t>
void print(t x, ll suc = 1) {
  cout << x;
  if (suc == 1) cout << "\n";
  if (suc == 2) cout << " ";
}
ll read() {
  ll i;
  cin >> i;
  return i;
}
vi readvi(ll n, ll off = 0) {
  vi v(n);
  for (ll i = ll(0); i < ll(n); i++) v[i] = read() + off;
  return v;
}
template <class T>
void print(const vector<T>& v, ll suc = 1) {
  for (ll i = ll(0); i < ll(v.size()); i++)
    print(v[i], i == ll(v.size()) - 1 ? suc : 2);
}
string readString() {
  string s;
  cin >> s;
  return s;
}
template <class T>
T sq(const T& t) {
  return t * t;
}
void yes(bool ex = true) {
  cout << "Yes"
       << "\n";
  if (ex) exit(0);
}
void no(bool ex = true) {
  cout << "No"
       << "\n";
  if (ex) exit(0);
}
void possible(bool ex = true) {
  cout << "Possible"
       << "\n";
  if (ex) exit(0);
}
void impossible(bool ex = true) {
  cout << "Impossible"
       << "\n";
  if (ex) exit(0);
}
constexpr ll ten(ll n) { return n == 0 ? 1 : ten(n - 1) * 10; }
const ll infLL = LLONG_MAX / 3;
const ll inf = infLL;
ll topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
ll topbit(ll t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
ll botbit(signed first) { return first == 0 ? 32 : __builtin_ctz(first); }
ll botbit(ll first) { return first == 0 ? 64 : __builtin_ctzll(first); }
ll popcount(signed t) { return __builtin_popcount(t); }
ll popcount(ll t) { return __builtin_popcountll(t); }
bool ispow2(ll i) { return i && (i & -i) == i; }
ll mask(ll i) { return (ll(1) << i) - 1; }
bool inc(ll first, ll second, ll c) { return first <= second && second <= c; }
template <class t>
void mkuni(vc<t>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
ll rand_int(ll l, ll r) {
  static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
  return uniform_int_distribution<ll>(l, r)(gen);
}
template <class t>
void myshuffle(vc<t>& first) {
  for (ll i = ll(0); i < ll(ll(first.size())); i++)
    swap(first[i], first[rand_int(0, i)]);
}
template <class t>
ll lwb(const vc<t>& v, const t& first) {
  return lower_bound(v.begin(), v.end(), first) - v.begin();
}
using uint = unsigned;
using ull = unsigned long long;
struct modinfo {
  uint mod, root;
};
template <modinfo const& ref>
struct modular {
  static constexpr uint const& mod = ref.mod;
  static modular root() { return modular(ref.root); }
  uint v;
  modular(ll vv = 0) { s(vv % mod + mod); }
  modular& s(uint vv) {
    v = vv < mod ? vv : vv - mod;
    return *this;
  }
  modular operator-() const { return modular() - *this; }
  modular& operator+=(const modular& rhs) { return s(v + rhs.v); }
  modular& operator-=(const modular& rhs) { return s(v + mod - rhs.v); }
  modular& operator*=(const modular& rhs) {
    v = ull(v) * rhs.v % mod;
    return *this;
  }
  modular& operator/=(const modular& rhs) { return *this *= rhs.inv(); }
  modular operator+(const modular& rhs) const { return modular(*this) += rhs; }
  modular operator-(const modular& rhs) const { return modular(*this) -= rhs; }
  modular operator*(const modular& rhs) const { return modular(*this) *= rhs; }
  modular operator/(const modular& rhs) const { return modular(*this) /= rhs; }
  modular pow(ll n) const {
    modular res(1), x(*this);
    while (n) {
      if (n & 1) res *= x;
      x *= x;
      n >>= 1;
    }
    return res;
  }
  modular inv() const { return pow(mod - 2); }
  friend modular operator+(ll x, const modular& y) { return modular(x) + y; }
  friend modular operator-(ll x, const modular& y) { return modular(x) - y; }
  friend modular operator*(ll x, const modular& y) { return modular(x) * y; }
  friend modular operator/(ll x, const modular& y) { return modular(x) / y; }
  friend ostream& operator<<(ostream& os, const modular& m) {
    return os << m.v;
  }
  friend istream& operator>>(istream& is, modular& m) {
    ll x;
    is >> x;
    m = modular(x);
    return is;
  }
  bool operator<(const modular& r) const { return v < r.v; }
  bool operator==(const modular& r) const { return v == r.v; }
  bool operator!=(const modular& r) const { return v != r.v; }
  explicit operator bool() const { return v; }
};
extern constexpr modinfo base{1000000007, 0};
using mint = modular<base>;
const ll vmax = (1 << 21) + 10;
mint fact[vmax], finv[vmax], invs[vmax];
void initfact() {
  fact[0] = 1;
  for (ll i = ll(1); i < ll(vmax); i++) {
    fact[i] = fact[i - 1] * i;
  }
  finv[vmax - 1] = fact[vmax - 1].inv();
  for (ll i = vmax - 2; i >= 0; i--) {
    finv[i] = finv[i + 1] * (i + 1);
  }
  for (ll i = vmax - 1; i >= 1; i--) {
    invs[i] = finv[i] * fact[i - 1];
  }
}
mint choose(ll n, ll k) { return fact[n] * finv[n - k] * finv[k]; }
mint binom(ll first, ll second) {
  return fact[first + second] * finv[first] * finv[second];
}
mint catalan(ll n) {
  return binom(n, n) - (n - 1 >= 0 ? binom(n - 1, n + 1) : 0);
}
ll gcd(ll first, ll second) {
  return second ? gcd(second, first % second) : first;
}
template <class num>
struct Vector {
  vector<num> v;
  Vector(ll s = 0) { v.resize(s, num(0)); }
  ll size() const { return v.size(); }
  num& operator[](ll i) { return v[i]; }
  num const& operator[](ll i) const { return v[i]; }
  Vector& operator+=(const Vector& rhs) {
    assert(size() == rhs.size());
    for (ll i = ll(0); i < ll(size()); i++) v[i] += rhs[i];
    return *this;
  }
  Vector& operator-=(const Vector& rhs) {
    assert(size() == rhs.size());
    for (ll i = ll(0); i < ll(size()); i++) v[i] -= rhs[i];
    return *this;
  }
  Vector& operator*=(const num& x) {
    for (ll i = ll(0); i < ll(size()); i++) v[i] *= x;
    return *this;
  }
  Vector& operator/=(const num& x) {
    num y = num(1) / x;
    for (ll i = ll(0); i < ll(size()); i++) v[i] *= y;
    return *this;
  }
  Vector operator+(const Vector& rhs) const { return Vector(*this) += rhs; }
  Vector operator-(const Vector& rhs) const { return Vector(*this) -= rhs; }
  Vector operator*(const num& x) const { return Vector(*this) *= x; }
  Vector operator/(const num& x) const { return Vector(*this) /= x; }
  bool operator==(const Vector& rhs) const { return v == rhs.v; }
};
template <class num>
num dot(const Vector<num>& first, const Vector<num>& second) {
  assert(first.size() == second.size());
  const ll s = first.size();
  num ans(0);
  for (ll i = ll(0); i < ll(s); i++) ans += first[i] * second[i];
  return ans;
}
template <class num>
ostream& operator<<(ostream& os, const Vector<num>& v) {
  return os << v.v;
}
template <class num>
struct Matrix {
  using V = Vector<num>;
  vector<V> m;
  Matrix(ll s = 0, num z = num(0)) {
    m.resize(s, V(s));
    for (ll i = ll(0); i < ll(size()); i++) m[i][i] = z;
  }
  ll size() const { return m.size(); }
  Matrix operator*(const Matrix& rhs) const {
    assert(size() == rhs.size());
    Matrix res(size());
    for (ll i = ll(0); i < ll(size()); i++)
      for (ll j = ll(0); j < ll(size()); j++)
        for (ll k = ll(0); k < ll(size()); k++)
          res[i][j] += m[i][k] * rhs[k][j];
    return res;
  }
  Matrix& operator*=(const Matrix& rhs) { return *this = (*this) * rhs; }
  V operator*(const V& rhs) const {
    assert(size() == rhs.size());
    V res(size());
    for (ll i = ll(0); i < ll(size()); i++) res[i] = dot(m[i], rhs);
    return res;
  }
  V& operator[](ll i) { return m[i]; }
  V const& operator[](ll i) const { return m[i]; }
  Matrix& operator/=(const num& r) {
    for (ll i = ll(0); i < ll(m.size()); i++) m[i] /= r;
    return *this;
  }
  Matrix operator/(const num& r) const { return Matrix(*this) /= r; }
  bool operator==(const Matrix& rhs) const { return m == rhs.m; }
};
template <class num>
ostream& operator<<(ostream& os, const Matrix<num>& x) {
  const ll s = x.size();
  os << "----------" << endl;
  for (ll i = ll(0); i < ll(s); i++) {
    for (ll j = ll(0); j < ll(s); j++) {
      os << x[i][j];
      if (j == s - 1) {
        os << endl;
      } else {
        os << " ";
      }
    }
  }
  return os << "----------";
}
template <class num>
num det(Matrix<num> first) {
  const ll s = first.size();
  num ans(1);
  for (ll i = ll(0); i < ll(s); i++) {
    for (ll j = ll(i + 1); j < ll(s); j++)
      if (first[j][i]) {
        ans = -ans;
        swap(first[j], first[i]);
        break;
      }
    if (!first[i][i]) return 0;
    ans *= first[i][i];
    for (ll j = ll(i + 1); j < ll(s); j++) {
      mint w = -first[j][i] / first[i][i];
      for (ll k = ll(i); k < ll(s); k++) first[j][k] += first[i][k] * w;
    }
  }
  return ans;
}
using V = Vector<mint>;
using M = Matrix<mint>;
M matpow(M first, ll n) {
  M res(ll(first.size()), 1);
  while (n) {
    if (n & 1) res *= first;
    first *= first;
    n >>= 1;
  }
  return res;
}
void slv() {
  ll n, k;
  cin >> n >> k;
  {
    ll g = gcd(n, k);
    n /= g;
    k /= g;
  }
  M x(5, 1), y(5, 1);
  x[1][4] = 1;
  x[2][0] = 1;
  x[3][1] = 1;
  y[0][0] = mint(2).inv();
  y[1][1] = mint(2).inv();
  M z;
  ll w = n, h = k;
  while (1) {
    if (w == 0) {
      z = matpow(y, h);
      break;
    } else if (h == 0) {
      z = matpow(x, w);
      break;
    } else if (w >= h) {
      y = matpow(x, w / h) * y;
      w %= h;
    } else {
      void(0);
      assert(w < h);
      x = x * matpow(y, h / w);
      h %= w;
    }
  }
  V tmp(5);
  tmp[0] = 1;
  tmp[4] = 1;
  V res = z * tmp;
  mint x0 = res[1] / (1 - res[0]);
  mint ans = x0 * res[2] + res[3];
  ans /= n;
  ans += 1;
  print(ans);
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
  ll t;
  cin >> t;
  for (ll _ = ll(0); _ < ll(t); _++) slv();
}

### Prompt

In Cpp, your task is to solve 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;
using ll = long long;
template <class t, class u>
void chmax(t& first, u second) {
  if (first < second) first = second;
}
template <class t, class u>
void chmin(t& first, u second) {
  if (second < first) first = second;
}
template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;
using pi = pair<ll, ll>;
using vi = vc<ll>;
template <class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
  return os << "{" << p.first << "," << p.second << "}";
}
template <class t>
ostream& operator<<(ostream& os, const vc<t>& v) {
  os << "{";
  for (auto e : v) os << e << ",";
  return os << "}";
}
using uint = unsigned;
using ull = unsigned long long;
template <class t, size_t n>
ostream& operator<<(ostream& os, const array<t, n>& first) {
  return os << vc<t>(first.begin(), first.end());
}
template <ll i, class T>
void print_tuple(ostream&, const T&) {}
template <ll i, class T, class H, class... Args>
void print_tuple(ostream& os, const T& t) {
  if (i) os << ",";
  os << get<i>(t);
  print_tuple<i + 1, T, Args...>(os, t);
}
template <class... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
  os << "{";
  print_tuple<0, tuple<Args...>, Args...>(os, t);
  return os << "}";
}
template <class t>
void print(t x, ll suc = 1) {
  cout << x;
  if (suc == 1) cout << "\n";
  if (suc == 2) cout << " ";
}
ll read() {
  ll i;
  cin >> i;
  return i;
}
vi readvi(ll n, ll off = 0) {
  vi v(n);
  for (ll i = ll(0); i < ll(n); i++) v[i] = read() + off;
  return v;
}
template <class T>
void print(const vector<T>& v, ll suc = 1) {
  for (ll i = ll(0); i < ll(v.size()); i++)
    print(v[i], i == ll(v.size()) - 1 ? suc : 2);
}
string readString() {
  string s;
  cin >> s;
  return s;
}
template <class T>
T sq(const T& t) {
  return t * t;
}
void yes(bool ex = true) {
  cout << "Yes"
       << "\n";
  if (ex) exit(0);
}
void no(bool ex = true) {
  cout << "No"
       << "\n";
  if (ex) exit(0);
}
void possible(bool ex = true) {
  cout << "Possible"
       << "\n";
  if (ex) exit(0);
}
void impossible(bool ex = true) {
  cout << "Impossible"
       << "\n";
  if (ex) exit(0);
}
constexpr ll ten(ll n) { return n == 0 ? 1 : ten(n - 1) * 10; }
const ll infLL = LLONG_MAX / 3;
const ll inf = infLL;
ll topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
ll topbit(ll t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
ll botbit(signed first) { return first == 0 ? 32 : __builtin_ctz(first); }
ll botbit(ll first) { return first == 0 ? 64 : __builtin_ctzll(first); }
ll popcount(signed t) { return __builtin_popcount(t); }
ll popcount(ll t) { return __builtin_popcountll(t); }
bool ispow2(ll i) { return i && (i & -i) == i; }
ll mask(ll i) { return (ll(1) << i) - 1; }
bool inc(ll first, ll second, ll c) { return first <= second && second <= c; }
template <class t>
void mkuni(vc<t>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
ll rand_int(ll l, ll r) {
  static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
  return uniform_int_distribution<ll>(l, r)(gen);
}
template <class t>
void myshuffle(vc<t>& first) {
  for (ll i = ll(0); i < ll(ll(first.size())); i++)
    swap(first[i], first[rand_int(0, i)]);
}
template <class t>
ll lwb(const vc<t>& v, const t& first) {
  return lower_bound(v.begin(), v.end(), first) - v.begin();
}
using uint = unsigned;
using ull = unsigned long long;
struct modinfo {
  uint mod, root;
};
template <modinfo const& ref>
struct modular {
  static constexpr uint const& mod = ref.mod;
  static modular root() { return modular(ref.root); }
  uint v;
  modular(ll vv = 0) { s(vv % mod + mod); }
  modular& s(uint vv) {
    v = vv < mod ? vv : vv - mod;
    return *this;
  }
  modular operator-() const { return modular() - *this; }
  modular& operator+=(const modular& rhs) { return s(v + rhs.v); }
  modular& operator-=(const modular& rhs) { return s(v + mod - rhs.v); }
  modular& operator*=(const modular& rhs) {
    v = ull(v) * rhs.v % mod;
    return *this;
  }
  modular& operator/=(const modular& rhs) { return *this *= rhs.inv(); }
  modular operator+(const modular& rhs) const { return modular(*this) += rhs; }
  modular operator-(const modular& rhs) const { return modular(*this) -= rhs; }
  modular operator*(const modular& rhs) const { return modular(*this) *= rhs; }
  modular operator/(const modular& rhs) const { return modular(*this) /= rhs; }
  modular pow(ll n) const {
    modular res(1), x(*this);
    while (n) {
      if (n & 1) res *= x;
      x *= x;
      n >>= 1;
    }
    return res;
  }
  modular inv() const { return pow(mod - 2); }
  friend modular operator+(ll x, const modular& y) { return modular(x) + y; }
  friend modular operator-(ll x, const modular& y) { return modular(x) - y; }
  friend modular operator*(ll x, const modular& y) { return modular(x) * y; }
  friend modular operator/(ll x, const modular& y) { return modular(x) / y; }
  friend ostream& operator<<(ostream& os, const modular& m) {
    return os << m.v;
  }
  friend istream& operator>>(istream& is, modular& m) {
    ll x;
    is >> x;
    m = modular(x);
    return is;
  }
  bool operator<(const modular& r) const { return v < r.v; }
  bool operator==(const modular& r) const { return v == r.v; }
  bool operator!=(const modular& r) const { return v != r.v; }
  explicit operator bool() const { return v; }
};
extern constexpr modinfo base{1000000007, 0};
using mint = modular<base>;
const ll vmax = (1 << 21) + 10;
mint fact[vmax], finv[vmax], invs[vmax];
void initfact() {
  fact[0] = 1;
  for (ll i = ll(1); i < ll(vmax); i++) {
    fact[i] = fact[i - 1] * i;
  }
  finv[vmax - 1] = fact[vmax - 1].inv();
  for (ll i = vmax - 2; i >= 0; i--) {
    finv[i] = finv[i + 1] * (i + 1);
  }
  for (ll i = vmax - 1; i >= 1; i--) {
    invs[i] = finv[i] * fact[i - 1];
  }
}
mint choose(ll n, ll k) { return fact[n] * finv[n - k] * finv[k]; }
mint binom(ll first, ll second) {
  return fact[first + second] * finv[first] * finv[second];
}
mint catalan(ll n) {
  return binom(n, n) - (n - 1 >= 0 ? binom(n - 1, n + 1) : 0);
}
ll gcd(ll first, ll second) {
  return second ? gcd(second, first % second) : first;
}
template <class num>
struct Vector {
  vector<num> v;
  Vector(ll s = 0) { v.resize(s, num(0)); }
  ll size() const { return v.size(); }
  num& operator[](ll i) { return v[i]; }
  num const& operator[](ll i) const { return v[i]; }
  Vector& operator+=(const Vector& rhs) {
    assert(size() == rhs.size());
    for (ll i = ll(0); i < ll(size()); i++) v[i] += rhs[i];
    return *this;
  }
  Vector& operator-=(const Vector& rhs) {
    assert(size() == rhs.size());
    for (ll i = ll(0); i < ll(size()); i++) v[i] -= rhs[i];
    return *this;
  }
  Vector& operator*=(const num& x) {
    for (ll i = ll(0); i < ll(size()); i++) v[i] *= x;
    return *this;
  }
  Vector& operator/=(const num& x) {
    num y = num(1) / x;
    for (ll i = ll(0); i < ll(size()); i++) v[i] *= y;
    return *this;
  }
  Vector operator+(const Vector& rhs) const { return Vector(*this) += rhs; }
  Vector operator-(const Vector& rhs) const { return Vector(*this) -= rhs; }
  Vector operator*(const num& x) const { return Vector(*this) *= x; }
  Vector operator/(const num& x) const { return Vector(*this) /= x; }
  bool operator==(const Vector& rhs) const { return v == rhs.v; }
};
template <class num>
num dot(const Vector<num>& first, const Vector<num>& second) {
  assert(first.size() == second.size());
  const ll s = first.size();
  num ans(0);
  for (ll i = ll(0); i < ll(s); i++) ans += first[i] * second[i];
  return ans;
}
template <class num>
ostream& operator<<(ostream& os, const Vector<num>& v) {
  return os << v.v;
}
template <class num>
struct Matrix {
  using V = Vector<num>;
  vector<V> m;
  Matrix(ll s = 0, num z = num(0)) {
    m.resize(s, V(s));
    for (ll i = ll(0); i < ll(size()); i++) m[i][i] = z;
  }
  ll size() const { return m.size(); }
  Matrix operator*(const Matrix& rhs) const {
    assert(size() == rhs.size());
    Matrix res(size());
    for (ll i = ll(0); i < ll(size()); i++)
      for (ll j = ll(0); j < ll(size()); j++)
        for (ll k = ll(0); k < ll(size()); k++)
          res[i][j] += m[i][k] * rhs[k][j];
    return res;
  }
  Matrix& operator*=(const Matrix& rhs) { return *this = (*this) * rhs; }
  V operator*(const V& rhs) const {
    assert(size() == rhs.size());
    V res(size());
    for (ll i = ll(0); i < ll(size()); i++) res[i] = dot(m[i], rhs);
    return res;
  }
  V& operator[](ll i) { return m[i]; }
  V const& operator[](ll i) const { return m[i]; }
  Matrix& operator/=(const num& r) {
    for (ll i = ll(0); i < ll(m.size()); i++) m[i] /= r;
    return *this;
  }
  Matrix operator/(const num& r) const { return Matrix(*this) /= r; }
  bool operator==(const Matrix& rhs) const { return m == rhs.m; }
};
template <class num>
ostream& operator<<(ostream& os, const Matrix<num>& x) {
  const ll s = x.size();
  os << "----------" << endl;
  for (ll i = ll(0); i < ll(s); i++) {
    for (ll j = ll(0); j < ll(s); j++) {
      os << x[i][j];
      if (j == s - 1) {
        os << endl;
      } else {
        os << " ";
      }
    }
  }
  return os << "----------";
}
template <class num>
num det(Matrix<num> first) {
  const ll s = first.size();
  num ans(1);
  for (ll i = ll(0); i < ll(s); i++) {
    for (ll j = ll(i + 1); j < ll(s); j++)
      if (first[j][i]) {
        ans = -ans;
        swap(first[j], first[i]);
        break;
      }
    if (!first[i][i]) return 0;
    ans *= first[i][i];
    for (ll j = ll(i + 1); j < ll(s); j++) {
      mint w = -first[j][i] / first[i][i];
      for (ll k = ll(i); k < ll(s); k++) first[j][k] += first[i][k] * w;
    }
  }
  return ans;
}
using V = Vector<mint>;
using M = Matrix<mint>;
M matpow(M first, ll n) {
  M res(ll(first.size()), 1);
  while (n) {
    if (n & 1) res *= first;
    first *= first;
    n >>= 1;
  }
  return res;
}
void slv() {
  ll n, k;
  cin >> n >> k;
  {
    ll g = gcd(n, k);
    n /= g;
    k /= g;
  }
  M x(5, 1), y(5, 1);
  x[1][4] = 1;
  x[2][0] = 1;
  x[3][1] = 1;
  y[0][0] = mint(2).inv();
  y[1][1] = mint(2).inv();
  M z;
  ll w = n, h = k;
  while (1) {
    if (w == 0) {
      z = matpow(y, h);
      break;
    } else if (h == 0) {
      z = matpow(x, w);
      break;
    } else if (w >= h) {
      y = matpow(x, w / h) * y;
      w %= h;
    } else {
      void(0);
      assert(w < h);
      x = x * matpow(y, h / w);
      h %= w;
    }
  }
  V tmp(5);
  tmp[0] = 1;
  tmp[4] = 1;
  V res = z * tmp;
  mint x0 = res[1] / (1 - res[0]);
  mint ans = x0 * res[2] + res[3];
  ans /= n;
  ans += 1;
  print(ans);
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
  ll t;
  cin >> t;
  for (ll _ = ll(0); _ < ll(t); _++) slv();
}

```