#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

#define lim 1000000
#define maxnrp 200

bool ciur[lim + 1];
vector <int> pri;

inline void CIUR()  {
    for(int i = 2;i <= lim;i++)
        if(!ciur[i])  {
            pri.push_back(i);
            for(long long j = 1LL * i * i;j <= lim;j++)
                ciur[j] = 1;
        }
}

inline unsigned long long sqrt(unsigned long long a)  {
    unsigned long long r = 0, pas = 1 << 30;
    while(pas)  {
        if((r + pas) * (r + pas) <= a)
            r += pas;
        pas >>= (unsigned long long)1;
    }
    return r;
}

unsigned long long A, B;
int v[maxnrp];

inline void desc()  {
    unsigned long long x = B, sqr = sqrt(B);
    v[0] = 0;
    for(int i = 0;x != 1 && pri[i] <= sqr;i++)
        if(x % pri[i] == 0)  {
            v[++v[0]] = pri[i];
            while(x % pri[i] == 0)
                x /= pri[i];
        }
    if(x != 1)  {
        v[++v[0]] = x;
    }
}

unsigned long long ans;

void back(int k, unsigned long long p, int nr)  {
    if(k == v[0] + 1)  {
        if(p != (unsigned long long)1)  {
            if(nr & 1)
                ans += A / p;
            else
                ans -= A / p;
        }
        return;
    }
    back(k + 1, p, nr);
    back(k + 1, p * v[k], nr + 1);
}

int main()  {
    int M;
    f >> M;
    CIUR();
    while(M)  {
        M--;
        ans = 0;
        f >> A >> B;
        desc();
        back(1, 1, 0);
        g << A - ans << "\n";
    }
    f.close(), g.close();
    return 0;
}