#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
int t, i, j, q, x, w, v[100005];
long long a, b, n, r, f, pr[105];
char s[100005];
int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);

    for(i=1;((i*i)<<1)+(i<<1)<=1000000;i++)
        if(!(s[i>>3]&(1<<(i&7))))
            for(j=((i*i)<<1)+(i<<1);(j<<1)+1<=1000000;j+=(i<<1)+1)
                s[j>>3]|=(1<<(j&7));
    for(i=1;(i<<1)+1<=1000000;i++)
        if(!(s[i>>3]&(1<<(i&7))))
            v[++q]=(i<<1)+1;
    // Ciur

    scanf("%d", &t);
    while(t--)
    {
        scanf("%lld%lld", &a, &b);
        i=0;
        x=0;
        while(b>1)
        {
            i++;
            if(i>q) break;
            j=0;
            while(!(b%v[i]))
            {
                b/=v[i];
                j=1;
            }
            if(j==1)
                pr[++x]=v[i];
        }
        if(b>1)
            pr[++x]=b;
        // Descompunere b

        n=1LL<<x;
        r=0;

        for(i=1;i<n;i++)
        {
            f=1;w=0;
            for(j=0;j<x;j++)
                if((i>>j)&1)
                {
                    f*=pr[j+1];
                    w++;
                }
            if(w%2)
                r+=a/f;
            else
                r-=a/f;
        }
        // Generare

        printf("%lld\n", a-r);
        //afisare
    }
    return 0;
}