第一

#include<bits/stdc++.h>
#define int long long
#define ll __int128
#define MULT_TEST 1
using namespace std;
const int mod = 1000000007;
const int N = 10000005;
const int inv61 = 166666668, inv62 = 833333345000000041;
int m, ans = 0, MOD, mu[N];
bool flag = 0;
vector<pair<int, int>> E;
inline int read() {
int w = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
w = (w << 1) + (w << 3) + ch - 48;
ch = getchar();
}
return w * f;
}
inline void Add(int &x, int y) {
x += y;
if (x >= MOD) x -= MOD;
}
inline void Del(int &x, int y) {
x -= y;
if (x < 0) x += MOD;
}
inline int Pow(int a, int b) {
int ans = 1;
if (a >= MOD) a %= MOD;
for (; b; b >>= 1) {
if (b & 1) ans = (ll)ans * a % MOD;
a = (ll)a * a % MOD;
}
return ans;
}
inline void Pre(int n) {
vector<int> P;
mu[1] = 1;
for (int i = 2; i <= n; i++) mu[i] = 2;
for (int i = 2; i <= n; i++) {
if (mu[i] == 2) mu[i] = -1, P.push_back(i);
for (auto p : P) {
if (i * p > n) break;
if (i % p) mu[i * p] = -mu[i];
else mu[i * p] = 0;
if (i % p == 0) break;
}
}
for (int i = 1; i <= n; i++) mu[i] += mu[i - 1];
}
inline int f(int n) {
if (n & 1) return (Pow(m - 1, n) - (m - 1) + MOD) % MOD;
else return (Pow(m - 1, n) + m - 1) % MOD;
}
inline int Color(int n) {
int ans1 = 0, ans2 = 0, ans3 = 0;
for (int l = 1, r = 0; l <= n; l = r + 1) {
r = n / (n / l);
Add(ans1, (ll)(mu[r] - mu[l - 1] + MOD) * (n / l) % MOD);
Add(ans2, (ll)(mu[r] - mu[l - 1] + MOD) * (n / l) % MOD * (n / l) % MOD);
Add(ans3, (ll)(mu[r] - mu[l - 1] + MOD) * (n / l) % MOD * (n / l) % MOD * (n / l) % MOD);
}
int inv = (flag ? inv62 : inv61);
return (ll)(ans3 + 3 * ans2 + 2 * ans1) % MOD * inv % MOD;
}
inline void Phi(int n) {
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
int t = 0;
while (n % i == 0) n /= i, t++;
E.push_back({i, t});
}
}
if (n > 1) E.push_back({n, 1});
}
inline void DFS(int dep, int d, int p) {
if (dep < 0) return Add(ans, (ll)p % MOD * f(d) % MOD), void();
auto [t, cnt] = E[dep];
DFS(dep - 1, d, p);
for (int i = 1; i <= cnt; i++, d /= t, p *= t)
DFS(dep - 1, d / t, p * (t - 1));
}
inline void Solve() {
int n, V;
vector<pair<int, int>>{}.swap(E);
n = read(); V = read();
flag = (n % mod == 0 ? true : false);
MOD = (flag ? mod * mod : mod);
Phi(n), m = Color(V), ans = 0;
int sz = E.size();
DFS(sz - 1, n, 1);
if (flag) ans /= mod, MOD = mod, ans = ans * Pow(n / MOD, MOD - 2) % MOD;
else ans = ans * Pow(n, MOD - 2) % MOD;
printf("%lld\n", ans);
}
signed main() {
int n;
n = read();
Pre(N - 5);
while (n--) Solve();
return 0;
}