#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");

vector <int> v;

int main()
{
    int m, i, n, numere, j;
    long long A, B, s;
    fin >> m;
    while(m--)
    {
        fin >> A >> B;
        v.clear();
        for(i = 2  ; i * i <= B ; i++)
        {
            if(B % i == 0)
            {
                v.push_back(i);
                while(B % i == 0)
                {
                    B /= i;
                }
            }
        }
        if(B != 1)
        {
            v.push_back(B);
        }
        n = v.size();
        s = 0;
        for(i = 0 ; i < (1 << n) ; i++)
        {
            long long nr = 1;
            numere = 0;
            for(j = 0 ; (1<<j) <= i ; j++)
            {
                if(i & (1<<j))
                {
                    numere++;
                    nr = 1ll * nr * v[j];
                }
            }
            if(numere % 2 == 0)
            {
                s += 1ll * A / nr;
            }
            else
            {
                s -= 1ll * A / nr;
            }
        }
        fout << s << "\n";
    }
}