#include <bits/stdc++.h>
#define int long long

using namespace std;

vector<int> d;
int desc(int n)
{
    d.clear();

    int div = 2;
    while(div * div <= n)
    {
        if(n % div == 0)
        {
            d.push_back(div);
            while(n % div == 0)
                n /= div;
        }
        if(div == 2) div++;
        else div += 2;
    }
    if(n > 1)
        d.push_back(n);
}

signed main()
{
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");
    int n;
    cin>>n;
    while(n--)
    {
        int a, b, suma = 0;
        cin>>a>>b;
        desc(b);

        for(int i=1; i < (1<<d.size()); i++)
        {
            int cnt = 0, prod = 1;
            for(int j = 0; j < d.size(); j++) {
                if(i & (1 << j)) {
                    cnt++;
                    prod *= d[j];
                }
            }
            if(cnt != 0)
                if(cnt % 2 == 0)
                    suma -= (a / prod);
                else
                    suma += (a/prod);
        }
        cout<<a - suma<<'\n';
    }



    return 0;
}