#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        int a,b;
        cin>>a>>b;
        vector <int> div;
        int cb=b,d=2;
        while(cb>1)
        {
            int cnt=0;
            while(cb%d==0&&cb>1)
            {
                cb/=d;cnt++;
            }
            if(cnt)
            {
                div.push_back(a/d);
            }
            d++;
            if(cb>1&&d*d>cb)d=cb;
        }
        int k=(1<<div.size());
        int sum=0;
        for(int i=1;i<k;i++)
        {
            int p=1,cnt=0;
            for(int 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;
}