#include <bits/stdc++.h>

using namespace std;
ifstream in("pinex.in");
ofstream out ("pinex.out");
long long v[1000009];
long long ciur(long long n)
{
    long long cnt = 0,i;
    for(i = 2; i * i <= n; i ++)
    {
        if(n % i == 0)
        {

            v[cnt] = i;
            cnt ++;
        }
        while(n % i == 0)
        {
            n = n / i;
        }
    }
    return cnt - 1;
}
int main()
{
    long long m,q,a,b,i,j;
    in >> m;
    for(q = 1; q <= m; q ++)
    {
        in >> a >> b;
        long long cnt = ciur(b),af = 0;
        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 * v[j];
                    nr_b ++;
                }
            }
            if(nr_b % 2 == 0)
            {
                af += a / aa;
            }
            else
            {
                af -= a / aa;
            }
        }
        out << af << '\n';
    }
    return 0;
}