#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 1000001

long long pr[80000],fact[20];
bool bit[20];
int nr ,n;

void ciur(){
    bool p[MAX];
    int i = 2;
    memset(p,0,sizeof(p));
    while(i <= 1000)
    {
        while(p[i])i++;
        for(int j=i*i;j < MAX;j+=i)p[j] = 1;
        i++;
    }
    for(int i=2;i<MAX;i++)if( !p[i] )pr[++nr] = i;
}

void desc(long long x){
    int i = 1;
    n = 0;
    while(x != 1 && i <= nr && pr[i] * pr[i] <= x)
    {
        if(x%pr[i] == 0)
        {
            fact[++n] = pr[i];
            while(x%pr[i] == 0)x/=pr[i];
        }
        i++;
    }
    if(x != 1)fact[++n] = x;
}

void cardinal(long long a){
    long long s = 0, pr = 1;
    int i ,nr = 0;
    memset(bit,0,sizeof(bit));
    while(bit[n+1] == 0)
    {
        i = 1;
        while(bit[i])
        {
            pr /= fact[i];
            bit[i] = 0;
            nr--;
            i++;
        }
            pr *= fact[i];
            bit[i] = 1;
            nr++;
        if(i <= n)
        if(nr%2) s += a/pr; else s -= a/pr;
    }
    printf("%lld\n",a-s);
}

int main(){
    int t;
    long long a,b;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);

    ciur();

        scanf("%d",&t);
        while(t--)
        {
            scanf("%lld %lld\n",&a,&b);
            desc(b);
           // for(int i=1;i<=n;i++)printf("%lld ",fact[i]); printf("\n");
            cardinal(a);
        }
    return 0;
}