#include <fstream>
#include <vector>
#include <bitset>
using namespace std;

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

const int N=10e6+2;
bitset<N>ciur;

void eratostene()
{
    ciur[1]=0;
    for(int i=2; i<=N; i++)
        if(!ciur[i])
            for(int j=i+i; j<=N; j+=i)
                ciur[j]=1;
}
void answer(long long a,long long b)
{
    vector<long long>divb;
    for(long long i=2; i*i<=b; i++)
        if(ciur[i]==0 && b%i==0)
        {
            divb.push_back(i);
            while(b%i==0)
                b/=i;
        }
    if(b!=1)
        divb.push_back(b);
    long long rez=a;
    long long submultimi=1<<divb.size();
    for(long long s=1; s<submultimi; s++)
    {
        int nrf=0;
        long long p=1;
        for(int k=0; k<divb.size(); k++)
        {
            if((1<<k) & s)
            {
                nrf++;
                p*=divb[k];
                if(p>a)
                    break;
            }
        }
        if(p<a)
        {
            if(nrf & 1)
                rez-=a/p;
            else
                rez+=a/p;
        }
    }
    cout<<rez<<'\n';
}
int main()
{
    eratostene();
    int m;
    long long a,b;
    cin>>m;
    while(m--)
    {
        cin>>a>>b;
        answer(a,b);
    }
    return 0;
}