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

using namespace std;

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

short m;
unsigned long long A , B;
int prim[100000];
unsigned long long a[25];
bool ciur[VALMAX + 5];

void Ciur()
{
    int 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(long long B , short &n)
{
    short d;

    for(d = 1 ; d <= prim[0] && 1ull * 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(short k , short cnt , long long prod , short n , long long &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(long long A , long long B)
{
    short n = 0;
    long long 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);
    }

    //cout << 1ll * 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37;

    return 0;
}