#include <cstdio>
using namespace std;
bool ciur[1000005];
long long prime[1000005] , v[105] , a , b , s;
void backt(int sign , int start , long long p)
{
    s = s + sign * (a / p);
    for(int i = start ; i <= v[0] ; i ++)
        backt(-sign , i + 1 , p * v[i]);
}
int main()
{
    freopen("pinex.in" , "r" , stdin);
    freopen("pinex.out" , "w" , stdout);
    int m , k , i , j;
    scanf("%d" , &m);
    for(i = 2 ; i * i <= 1000000 ; i ++)
        if(!ciur[i])
            for(j = i * i ; j <= 1000000 ; j = j + i)
                ciur[j] = 1;
    for(i = 2 ; i <= 1000000 ; i ++)
        if(!ciur[i])
            prime[++ prime[0]] = i;
    for(k = 1 ; k <= m ; k ++)
    {
        scanf("%lld%lld" , &a , &b);
        i = 1;
        v[0] = 0;
        while(prime[i] * prime[i] <= b)
        {
            int exp = 0;
            while(b % prime[i] == 0)
            {
                b = b / prime[i];
                exp ++;
            }
            if(exp > 0)
                v[++ v[0]] = prime[i];
            i ++;
        }
        if(b > 1)
            v[++ v[0]] = b;
        s = 0;
        backt(1 , 1 , 1);
        printf("%lld\n" , s);
    }
    return 0;
}