#include <bits/stdc++.h>

using namespace std;

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

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

        if(div == 2) div++;
        else div += 2;
    }
}

string to_binary(int n)
{
    string k = "";
    while(n>0)
    {
        k += (n%2 + '0');
        n/=2;
    }

    while(k.size() < 6)
        k += '0';

    return k;
}

int 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++)
        {
            string k = to_binary(i);

            int cnt = 0, prod = 1;
            for(int j=0; j<min(k.size(), d.size()); j++)
                if(k[j] == '1')
                {
                    cnt ++;
                    prod *= d[j];
                }

            if(cnt != 0)
                if(cnt % 2 == 0)
                    suma -= (a / prod);
                else
                    suma += (a/prod);
        }

        cout<<a - suma<<'\n';
    }



    return 0;
}