#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
int main()
{
    long long t;
    cin>>t;
    for(long long i=0;i<t;i++)
    {
        long long a,b;
        cin>>a>>b;
        vector <long long> div;
        long long cb=b,d=2;
        while(cb>1)
        {
            long long cnt=0;
            while(cb%d==0&&cb>1)
            {
                cb/=d;cnt++;
            }
            if(cnt)
            {
                div.push_back(d);
            }
            d++;
            if(cb>1&&d*d>cb)d=cb;
        }
        long long k=(1<<div.size());
        long long sum=0;
        for(long long i=1;i<k;i++)
        {
            long long p=1,cnt=0;
            for(long long j=0;j<div.size();j++)
            {
                if(i & (1<<j))
                {
                    cnt++;
                    p*=div[j];
                }
            }
            if(p>a)continue;
            if(cnt%2==1)sum+=a/p;
            else sum-=a/p;
        }
        cout<<a-sum<<endl;
    }
    return 0;
}