#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128;
using u128 = unsigned __int128;
template <typename T>
void chkmax(T &x, const T &y) {
  if (x < y) x = y;
}
template <typename T>
void chkmin(T &x, const T &y) {
  if (y < x) x = y;
}
ll p;
ld ip;
ll mul(ll x, ll y) {
  ll ret = (ull)x * y - (ull)(x * ip * y + 0.5) * p;
  return ret < 0 ? ret + p : ret;
}
ll qpow(ll x, ll y) {
  ll ret = 1;
  for (; y; y >>= 1, x = mul(x, x))
    if (y & 1) ret = mul(ret, x);
  return ret;
}
constexpr int MAXT = 1e6 + 10;
int val[MAXT * 4], sum1[MAXT * 4], sum2[MAXT * 4];
ll lgd(ll a) {
  ll ret = qpow(a, (p - 1) / 2);
  return ret == p - 1 ? -1 : ret;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int cas;
  cin >> cas;
  while (cas--) {
    ll t;
    cin >> p >> t;
    ip = 1.0l / p;
    chkmin(t, (p - 2) / 2);
    for (int i = 0; i <= t * 4; ++i) val[i] = lgd(p - t * 2 + i);
    partial_sum(val, val + t * 4, sum1);
    sum2[0] = val[0];
    sum2[1] = val[1];
    for (int i = 2; i < t * 4; ++i) sum2[i] = sum2[i - 2] + val[i];
    ll ans = 0;
    for (int d = 1; d <= t; ++d) ans += p - 4 - val[t * 2 + d] * val[t * 2 + d * 2];
    for (int i = 0; i < t * 2; ++i) {
      int lb = (t * 2 - i + 1) / 2;
      ans -= t - lb + 1 +
             val[i] * (sum1[i + t] - sum1[i + lb - 1] + sum2[i + t * 2] -
                       sum2[i + (lb - 1) * 2]);
    }
    for (int i = 0; i < t * 4; ++i) {
      int lb = max({i - t * 2 + 1, 1ll, t * 2 - i});
      int rb = min({t * 4 - 1 - i, t, (ll)i});
      if (lb <= rb) ans -= val[i] * (sum1[i + rb] - sum1[i + lb - 1]);
    }
    cout << ans / 4 << "\n";
  }
  return 0;
}
/*
g++ K.cpp -o K -std=c++14 -O2 -Wall -Wextra -Wshadow -g
-fsanitize=address,undefined
*/
/*
1
7 32
*/