/**
 ____ ____ ____ ____ ____
||O |||M |||E |||G |||A ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|


Se spune ca sunt vise
Si ca nu pot fi atinse
Sunt primele ce le vezi cand becurile-s stinse
Dar si cand is aprinse
Cand te trezesti cu ele-n gand
Si le vizualizezi din nou rand pe rand
Se spune ca visezi daca stai si-ti imaginezi
Ca esti altfel decat ceilalti, dar nu tre sa crezi
Continua sa lupti altfel imi vei da dreptate
Vei bea pe spate cu gandul la vise spulberate
    - "Vise" - Nane -

**/
#include<bits/stdc++.h>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
void solve(){
    long long a,b,nr(0);
    fin>>a>>b;
    a--;
    vector<long long>f;
    for(long long i=2;i*i<=b;i++){
        if(b%i==0)f.push_back(i);
        while(b%i==0)b/=i;
    }
    if(b>1)f.push_back(b);
    for(long long i=1;i<(1<<f.size());i++){
        long long bt(0),p(1);
        for(long long j=0;j<f.size();j++){
            if(i&(1<<j))bt++,p*=f[j];
        }
        nr+=((bt&1)?a/p:-a/p);
    }
    fout<<a-nr<<"\n";
}
int main(){
    long long q;
    fin>>q;
    while(q--)solve();
    return 0;
}