/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;

vector <long long> divs;

int main()
{
    ifstream fin("pinex.in");
    ofstream fout("pinex.out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long q,i,x,y,d,mask,cnt,ans,product,j;
    fin >> q;
    for (i=1;i<=q;i++)
    {
        fin >> y >> x;
        divs.clear();
        d=1;
        while (x!=1 && d*d<=x)
        {
            d++;
            if (x%d==0)
            {
                while (x%d==0)
                       x=x/d;
                divs.push_back(d);
            }
        }
        if (x!=1)
            divs.push_back(x);
        ans=0;
        for (mask=1;mask<(1<<(divs.size()));mask++)
        {
             cnt=0;
             product=1;
             for (j=0;j<divs.size();j++)
             {
                  if (mask&(1<<j))
                  {
                      product=product*(divs[j]);
                      cnt++;
                  }
             }
             if (cnt%2==1)
             {
                 ans+=(y-product)/product+1;
             }
             else
             {
                 ans-=(y-product)/product+1;
             }
        }
        fout << y-ans << "\n";
    }
}