#include <bits/stdc++.h>
const int PMAX = 1000005;
using namespace std;

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

bool ok[PMAX];
int prime[PMAX];
long long f[PMAX];

void ciur()
{
    int k=0;
    prime[++k]=2;
    for(int i=3; i<PMAX; i+=2)
        if(ok[i]==0) {
            prime[++k]=i;
            for(int j=3*i; j<=PMAX; j+=2*i)
                ok[j]=1;
        }
}
int main()
{
    int t;
    long long a, b, d, k;
    fin>>t;
    ciur();
    while(t--) {
        k=d=0;
        fin>>a>>b;
        while(b>1) {
            d++;
            if(b%prime[d]==0) {
                f[++k]=prime[d];
                while(b%prime[d]==0)
                    b/=prime[d];
            }
            if(prime[d]>sqrtl(b) && b>1) {
                f[++k]=b;
                b=1;
            }
        }
        if(b>1)
            f[k]=b;
        long long sol=a;
        for(int i=1; i<(1<<k); i++) {
            long long nr=0, prod=1;
            for (int j=0; j<k; j++)
                if ((1<<j)&i) {
                    prod=1LL*prod*f[j+1];
                    nr++;
                }
            if (nr%2)
                nr=-1;
            else nr=1;
            sol=sol+1LL*nr*a/prod;
        }
        fout<<sol<<'\n';
    }
    return 0;
}