#include <fstream>
#include <cmath>

using namespace std;

ifstream cin ("pinex.in");
ofstream cout ("pinex.out");

long long int dv[30];

int main()
{
    int q,i,j,k;
    long long int a,b,t,d,c,nr,prd,p;
    cin >> q;
    for (i=0; i<q; i++){
        cin >> a >> b;
        t=0;
        d=2;
        c=b;
        while (c>1){
            if (c%d==0){
                dv[++t]=d;
                while (c%d==0)
                    c/=d;
            }
            if (sqrt(c)<d && c>1){
                dv[++t]=c;
                c=1;
            }
            if (d==2)
                d++;
            else
                d+=2;
        }
        p=a;
        for (j=1; j<(1<<t); j++){
            nr=0;
            prd=1;
            for (k=0; k<t; k++)
                if ((1<<k)&j){
                    prd*=dv[k+1];
                    nr++;
                }
            if (nr%2)
                nr=-1;
            else
                nr=1;
            p+=nr*(a/prd);
        }
        cout << p << '\n';
    }
    return 0;
}