#include <fstream>
using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long di[300000];
long long bdiv[300000];
int d[300000];
short int ex[1000004];
long long suma = 0,ct, a,sign;
long long prod = 1;

void bkt(int l)
{
    if(l < ct + 1)
    {
        int start = d[l - 1] + 1;
        for(int i = start; i <= ct; i++)
        {
            d[l] = i;
            prod*=bdiv[d[l]];
            sign = 1;
            if(l%2 == 0)
                sign = -1;
            suma += (sign*(a/prod));
            bkt(l+1);
            prod/=bdiv[d[l]];
        }
    }
}

int main()
{
    int m;
    long long b;
    fin>>m;
    di[1] = 2;
    int cnt = 1;
    for(long long i = 3; i <= 1000002; i += 2)
    {
        if(ex[i] == 0)
        {
            di[++cnt] = i;
            for(long long  j = i*i; j <= 1000002; j+=i)
                ex[j] = 1;
        }
    }
    for(int j = m; j != 0; j--)
    {
        suma = 0;
        prod = 1;
        fin>>a>>b;
        ct = 0;
        for(int i = 1; di[i] * di[i] <= b;i++)
        {
            if(b%di[i]==0){
                bdiv[++ct] = di[i];
                d[ct] = 0;
                b/=di[i];
            }
            while(b%di[i]==0){
                b/=di[i];
            }
        }
        if(b!=1)
            bdiv[++ct]= b;
        d[ct] = 0;
        bkt(1);
        fout<<a-suma<<"\n";
    }
    return 0;
}