#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(unsigned long long B , short &n)
{
    short 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(short k , short cnt , unsigned long long prod , short n , unsigned 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[k] <= A)
            bkt(k + 1 , cnt + 1 , prod * a[k] , n , ans);
    }
}

void Query(unsigned long long A , unsigned long long B)
{
    short n = 0;
    unsigned 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);
    }

    return 0;
}