#include <iostream>
#include <fstream>
#include <bitset>
#define LIM 1000000

using namespace std;

ifstream fin  ("pinex.in");
ofstream fout ("pinex.out");

bitset <1000005> f;
int prm, p[80000];

int n, nrd;
long long a, b, sol, d[100005];

void dvd(long long &nr, int x){
    int e=0;
    while(nr%x == 0){
        e++;
        nr/=x;
    }
    if(e != 0)
        d[++nrd]=x;
}

void bt(int k, int lst, int cnt, long long prd){

    if(k > 1){
        if(cnt%2 == 1)
            sol += a/prd;
        else
            sol -= a/prd;
    }

    if(k > nrd)
        return;

    for(int i=lst+1; i<=nrd; i++)
        bt(k+1, i, cnt+1, prd*d[i]);
}

int main (){
    f[0]=f[1]=1;
    for(int i=4; i<=LIM; i+=2)
        f[i]=1;
    for(int i=3; i<=LIM/i; i+=2)
        if(f[i] == 0)
            for(int j=i*i; j<=LIM; j+=i)
                f[j]=1;

    p[++prm]=2;
    for(int i=3; i<=LIM; i+=2)
        if(f[i] == 0)
            p[++prm]=i;


    fin>>n;
    while(n--){
        fin>>a>>b;
        sol=0;
        nrd=0;

        for(int i=1; p[i] <= b / p[i] && i <= prm && b != 1; i++)
            dvd(b, p[i]);

        if(b != 1)
            d[++nrd]=b;

        bt(1, 0, 0, 1);
        fout<<a-sol<<"\n";
    }
    return 0;
}