#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define maxn 1000005
#define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define maxb ((1<<8)+5)
#define ll long long
#define sti string
#define int long long

using namespace std;

const int MAX=1e6;
int prime[maxn];
const int mod=1e9+7;
vector<int> primes;
int n,k,test;

void prepare(){
   for(int i=2;i<=MAX;i++) prime[i]=1;
   for(int i=2;i*i<=MAX;i++){
      if(prime[i]){
        for(int j=2*i;j<=MAX;j+=i) prime[j]=0;
      }
   }
   for(int i=2;i<=MAX;i++) if(prime[i]) primes.push_back(i);
}

int power(int a,int b){
  int res=1;
  while(b){
     if(b&1) res=res*a%mod;
     a=a*a%mod;
     b>>=1;
  }
  return res;
}

signed main() {
    itachi
    freopen("stablecomplex.inp","r",stdin);
    freopen("stablecomplex.out","w",stdout);
    prepare();
    cin>>test;
    while(test--){
        cin>>n>>k;
        if(k==1){
            cout<<(power(2,n)-1+mod)%mod<<'\n';
            continue;
        }
        vector<int> divi;
        for(int x : primes){
            if(k%x==0){
                int cur=1;
                while(k%x==0){
                    cur*=x;
                    k/=x;
                }
                divi.push_back(cur);
            }
        }
        if(k>1) divi.push_back(k);
        bool zero=0;
        for(int x : divi){
            if( x > n) {
                zero=1;
                break;
            }
        }
        if(zero){
            cout<<0<<'\n';
            continue;
        }
        vector<int> Lcm(((1<<divi.size())+5),0);
        vector<int> cnt(((1<<divi.size())+5),0);
        Lcm[0]=1;
        cnt[0]=n;
        for(int mask=1;mask<(1<<divi.size());mask++){
            int j=__builtin_ctz(mask);
            if(Lcm[mask^(1<<j)] > n / divi[j]) Lcm[mask]=n+1;
            else Lcm[mask]=Lcm[mask^(1<<j)]*divi[j];
            cnt[mask]=n/Lcm[mask];
        }

        for(int i=0;i<divi.size();i++){
            for(int mask=0;mask<(1<<divi.size());mask++){
                if((mask>>i)&1){
                    cnt[mask^(1<<i)] -= cnt[mask];
                }
            }
        }

        vector<int> num=cnt;
        for(int i=0;i<divi.size();i++){
            for(int mask=0;mask<(1<<divi.size());mask++){
                if((mask>>i)&1){
                    num[mask] += num[mask^(1<<i)];
                }
            }
        }

        int res=0;
        for(int mask=0;mask<(1<<divi.size());mask++){
            int Count=power(2,num[mask]);
            if((divi.size() - __builtin_popcountll(mask))%2==1){
                res=(res-Count+mod)%mod;
            }
            else res=(res+Count)%mod;
        }
        cout<<res<<'\n';
    }
    return 0;
}