#include <bits/stdc++.h>

using namespace std;

ifstream fin  ("pinex.in");
ofstream fout ("pinex.out");

const int LIM = 1000000;
bitset <LIM + 5> ciur;
int pcnt, pnum[80000];
void mark(int px){
    for(int i=px*px; i<=LIM; i+=px)
        ciur[i] = true;
}

long long p, e, prim[100];
long long n, m, x, sol, prd, cnt;

void divd(long long d){
    long long e = 0;
    while(m % d == 0){
        e++;
        m /= d;
    }
    if(e != 0)
        prim[p++] = d;
}

signed main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    ciur[0] = ciur[1] = true;
    mark(2);
    mark(3);
    for(int i=5; i<=LIM/i; i+=6){
        if(!ciur[i]) mark(i);
        if(!ciur[i+2]) mark(i+2);
    }
    pnum[++pcnt] = 2;
    pnum[++pcnt] = 3;
    for(int i=5; i<=LIM; i+=6){
        if(!ciur[i]) pnum[++pcnt] = i;
        if(!ciur[i+2]) pnum[++pcnt] = i+2;
    }

    long long teste;
    fin>>teste;
    while(teste--){
        fin>>n>>x;

        p = 0;
        for(int i=1; i<=pcnt && pnum[i] <= x / pnum[i]; i++){
            e = 0;
            while(x % pnum[i] == 0){
                e = 1;
                x /= pnum[i];
            }
            if(e != 0)
                prim[p++] = pnum[i];
        }
        if(x > 1)
            prim[p++] = x;

        sol = 0;
        for(long long mask=1; mask < (1<<p); mask++){
            prd = 1;
            cnt = 0;
            for(long long i=0; i < p; i++)
                if(mask & (1<<i)){
                    prd *= prim[i];
                    cnt++;
                }
            if(cnt&1)
                sol += n / prd;
            else
                sol -= n / prd;
        }
        fout<<n-sol<<"\n";
    }
    return 0;
}