#include <fstream>
#include <cstring>
#include <bitset>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
bitset<1000001>f;
int w[100];
long long a,b,b1,sol,k,i,j,p,m,z[100],v[300000],sol1,q,t;
int main(){
    fin>>m;
    for(i=2;i<=1000000;i++)
        if(!f[i]){
            v[++p] = i;
            for (j=i+i;j<=1000000;j+=i)
                f[j] = 1;
        }
    for(t=1;t<=m;t++) {
        fin>>a>>b;
        b1 = b;
        k = 0;
        for (i=1;v[i]*v[i]<=b && b1!=1;i++) {
            if (b1%v[i] == 0) {
                z[++k] = v[i];
                while (b1%v[i] == 0)
                    b1/=v[i];
            }
        }
        if (b1!=1) {
            z[++k] = b1;
        }
        memset(w, 0, sizeof(w));
        sol = 0;
        while(!w[0]){
            j = k;
            while (w[j] == 1) {
                w[j] = 0;
                j--;
            }
            w[j] = 1;
            if (j == 0)
                break;
            q = 0;
            sol1 = 1;
            for (j=1;j<=k;j++) {
                q+=w[j];
                if (w[j])
                sol1 *= z[j];
            }
            if (q%2==1)
                sol += a/sol1;
            else
                sol -= a/sol1;
        }
        if (sol > 0)
            fout<<a-sol<<"\n";
        else
            fout<<a+sol<<"\n";
    }

    return 0;
}