#include <bits/stdc++.h>
#define VALMAX 1000000
#define ull unsigned long long

using namespace std;

ifstream f ("pinex.in");
ofstream g ("pinex.out");

ull m;
ull A , B;
ull prim[100000];
ull a[25];
ull ciur[VALMAX + 5];

void Ciur()
{
    ull i , j;

    ciur[0] = ciur[1] = 1;
    prim[++prim[0]] = 2;

    for(i = 3 ; i <= VALMAX ; i += 2)
        if(!ciur[i])
        {
            prim[++prim[0]] = i;

            for(j = 2 * i ; j <= VALMAX ; j += i)
                ciur[j] = 1;
        }
}

void GetDiv(ull B , ull &n)
{
    ull d;

    for(d = 1 ; d <= prim[0] && 1ll * prim[d] * prim[d] <= B ; d++)
    {
        if(B % prim[d] == 0)
        {
            a[++n] = prim[d];

            while(B % prim[d] == 0)
                B /= prim[d];
        }
    }

    if(B > 1)
        a[++n] = B;
}

void bkt(ull k , ull cnt , ull prod , ull n , ull &ans)
{
    if(k == n + 1)
    {
        if(!cnt)
            return;

        if(cnt % 2 == 1)
            ans += A / prod;
        else ans -= A / prod;
    }
    else
    {
        bkt(k + 1 , cnt , prod , n , ans);

        if(prod <= A / a[k])
            bkt(k + 1 , cnt + 1 , prod * a[k] , n , ans);
    }
}

void Query(ull A , ull B)
{
    ull n = 0;
    ull ans = 0;

    GetDiv(B , n);
    bkt(1 , 0 , 1 , n , ans);

    g << A - ans << '\n';
}

int main()
{
    Ciur();

    f >> m;

    while(m--)
    {
        f >> A >> B;
        Query(A , B);
    }

    return 0;
}