#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long modpow(long long a, long long b){
	long long ans = 1;
	while (b > 0){
		if (b % 2 == 1){
			ans *= a;
			ans %= MOD;
		}
		a *= a;
		a %= MOD;
		b /= 2;
	}
	return ans;
}
long long modinv(long long a){
	return modpow(a, MOD - 2);
}
long long dfs(int C, vector<pair<int, int>> &G, int g, int cnt, int p){
  if (p == G.size()){
    return modpow(C, g * 2) * cnt % MOD;
  } else {
    int f = G[p].first;
    int c = G[p].second;
    long long ans = 0;
    for (int i = 0; i <= c; i++){
      if (i < c){
        ans += dfs(C, G, g, cnt / f * (f - 1), p + 1);
        g *= f;
        cnt /= f;
      } else {
        ans += dfs(C, G, g, cnt, p + 1);
      }
    }
    ans %= MOD;
    return ans;
  }
}
int main(){
  int T;
  cin >> T;
  for (int i = 0; i < T; i++){
    int N, C;
    cin >> N >> C;
    int N2 = N;
    vector<pair<int, int>> F;
    for (int j = 2; j * j <= N2; j++){
      if (N2 % j == 0){
        int cnt = 0;
        while (N2 % j == 0){
          N2 /= j;
          cnt++;
        }
        F.push_back(make_pair(j, cnt));
      }
    }
    if (N2 > 1){
      F.push_back(make_pair(N2, 1));
    }
    long long sum = dfs(C, F, 1, N, 0);
    sum += modpow(C, N) * N % MOD;
    long long ans = sum * modinv(N * 2) % MOD;
    cout << ans << endl;
  }
}