#include <fstream>
#include <bitset>

using namespace std;

bitset<1000005> viz;
int prime[160005];
int poz;

inline void erat()
{
    for(int i=3;(i*i)<1005;i+=2)
        if(!viz[i])
            for(int j=i*i;j<1000005;j+=i)
                viz[j]=1;

    prime[++poz]=2;
    for(int i=3;i<1000005;i+=2)
        if(!viz[i])
            prime[++poz]=i;
}

long long int v[25];
int fact;

inline void desc(int x)
{
    fact=0;
    for(int i=1;(1ll*prime[i]*prime[i])<=x;i++)
        if(x%prime[i]==0){
            v[++fact]=prime[i];
            while(x%prime[i]==0)
                x/=prime[i];
        }

    if(x>1)
        v[++fact]=x;
}

long long int pinex(int a)
{
    long long int ans=0;
    for(int i=1;i<(1<<fact);i++){
        long long int nr=1;
        int semn=0;

        for(int j=0;j<fact;j++)
            if(i&(1<<j)){
                semn^=1;
                nr*=v[j+1];
            }

        if(!semn)
            semn=-1;
        ans+=(semn*(a/nr));
    }

    return ans;
}

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

    erat();

    int m=0;
    cin>>m;

    long long int a,b;
    while(m--){
        cin>>a>>b;
        desc(b);

        cout<<a-pinex(a)<<'\n';
    }

    cin.close();
    cout.close();
    return 0;
}