#include <bits/stdc++.h>

using namespace std;
ifstream in("1.in");
ofstream out ("1.out");
long long v[1000009],p[1000009],num,aok[1000009];
long long ciur()
{
    long long i,j,cnt = 0;
    v[1] = 1;
    v[0] = 1;
    for(i = 2; i <= 1000009; i ++)
    {
        if(!v[i])
        {
            p[cnt] = i;
            cnt ++;
            for(j = i * 2;j <= 1000009; j += i)
            {
                v[j] = 1;
            }
        }
    }
    return cnt - 1;
}
long long c2(long long n)
{
    long long cnt = 0,i;
    for(i = 0; i <= num; i ++)
    {
        if(n % p[i] == 0)
        {
            aok[cnt] = p[i];
            cnt ++;
        }
        while(n % p[i] == 0)
        {
            n = n / p[i];
        }
        if(n == 1)
        {
            break;
        }
    }
    if(n > 1)
    {
        aok[cnt] = n;
        cnt ++;
    }
    return cnt - 1;
}
int main()
{
    long long m,q,a,b,i,j;
    in >> m;
    num = ciur();
    for(q = 1; q <= m; q ++)
    {
        in >> a >> b;
        long long af = 0,cnt = c2(b);
        for(i = 0; i < 1 << (cnt + 1); i ++)
        {
            long long aa = 1;
            long long nr_b = 0;
            for(j = 0; j <= cnt; j ++)
            {
                if((i >> j) & 1)
                {
                    aa = aa * aok[j];
                    nr_b ++;
                }
            }
            if(nr_b % 2 == 0)
            {
                af += a / aa;
            }
            else
            {
                af -= a / aa;
            }
        }
        out << af << '\n';
    }
    return 0;
}