#include <cstdio>
#define MAX 1000000
using namespace std;
bool ciur[MAX+1];
int prime[MAX+1],k, st[MAX+1], n;
void ciuruire()
{
    int prim=2;
    while(prim*prim<=MAX)
    {
        prime[++k]=prim;
        for(int i=prim;i*prim<=MAX;++i)
            ciur[i*prim]=1;
        prim++;
        while(ciur[prim])
            prim++;
    }
    for(int i=prim;i<=MAX;++i)
        if(!ciur[i])
            prime[++k]=i;
}
inline int biti(int x)
{
    int nr=0;
    for(int i=0;(1<<i)<n;++i)
        if((1<<i)&(x))
            nr++;
    return nr;
}
inline long long produs(int x)
{
    long long p=1;
    for(int i=0;(1<<i)<n;++i)
        if((1<<i)&(x))
            p*=st[i+1];
    return p;
}
inline long long calc(long long a, long long b)
{
    long long nr=0;
    n=0;
    for(int i=1;i<=k && b!=1;++i)
    {
        if(b%prime[i] == 0){
            st[++n]=prime[i];
            b/=prime[i];
        }
    }
    if(b!=1)
        st[++n]=b;
    for(int i=1;i<(1<<n);++i)
    {
        if(biti(i)%2==0)
            nr-=a/produs(i);
        else nr+=a/produs(i);
    }
    return a-nr;
}
int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    long long m, a, b;
    ciuruire();
    for(int i=1;i<=m;++i)
    {
        scanf("%lld%lld", &a, &b);
        printf("%lld\n", calc(a, b));
    }
    return 0;
}