#include <bits/stdc++.h>
#define MAX 1000010
#define ll long long
using namespace std;
ifstream f ("pinex.in");
ofstream g ("pinex.out") ;
bool prim[MAX];
ll a[MAX],N ,  A , B , t = 0 , sol[1001] , nr , prod , S = 0 , m = 0 , j ;
int main()
{
    prim[0] = prim[1] = true ;
    for (ll i = 2; i*i < 1000000 ; i ++)
    {
        if (!prim[i])
        {
            t ++ ;
            a[t] = i;
         for (ll j = i * 2 ;j <= 1000000 ; j += i)
                prim[j] = true ;
        }

    }
    for (ll i = 1000; i <= 1000000 ; i ++)
        if (prim[i] == 0)
    {
        t ++ ;
        a[t] = i;

    }

    f >> N ;

    for (ll k = 1 ; k <= N ; k ++)
    {
        f >> A >> B ;

          m =0 , j = 1 , S= 0 ;
         while (a[j] * a[j] <= B)
         {
             if (B % a[j] == 0)
             {
                 while (B % a[j] == 0)
                    B /= a[j] ;
                 m ++ ;
                 sol[m] = a[j] ;
             }
             j ++ ;
         }
         if  (B != 1) {m ++ ; sol[m] = B;}


    for (ll i = 1 ; i < (1 << m) ; i ++ )
    {
        nr = 0 ;
        prod = 1 ;
        for (ll j = 0 ; j < m ; j++)
            if ((i & (1<<j)))
            {
                nr ++ ;
                prod *= sol[j+1] ;
            }

        if (nr % 2 == 1) S += A/prod;
        else S -= A/prod;

    }
     g << A-S << '\n';
    }
    return 0 ;
}