#include <bits/stdc++.h>

using namespace std;

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

int t, a, b, sol;
int m, e, d[20];
int f[20];

void bt(int k, int crt, int lst){
    if(k > 1){
        if((k-1)%2 == 1)
            sol += a/crt;
        else
            sol -= a/crt;
        if(k > m)
            return;
    }

    for(int i=lst+1; i<=m; i++)
        bt(k+1, crt*d[i], i);
}

int main (){
    fin>>t;
    for(int test=1; test<=t; test++){
        fin>>a>>b;
        m=0; sol=0;

        e=0;
        while(b%2 == 0){
            e++;
            b/=2;
        }
        if(e != 0)
            d[++m]=2;
        for(int i=3; i<=b/i; i++){
            e=0;
            while(b%i == 0){
                e++;
                b/=i;
            }
            if(e != 0)
                d[++m]=i;
        }
        if(b != 1)
            d[++m]=b;

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


    return 0;
}