#include <bits/stdc++.h>
using namespace std;
const int VMAX = 1e6+2;
bool ciur[VMAX];
vector<int> prime;
int m,a,b;

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

int main()
{
    ciur[0] = ciur[1] = 1;
    for(int i = 2; i < VMAX; i++){
        if(ciur[i] == 0){
            prime.push_back(i);
            for(int j = 2*i; j < VMAX; j += i){
                ciur[j] = 1;
            }
        }
    }
    fin >> m;
    while(m--){
        fin >> a >> b;
        vector<int> baze;
        int ind = 0;
        while(ind < prime.size() && b > 1){
            if(b%prime[ind] == 0){
                while(b%prime[ind] == 0){
                    b /= prime[ind];
                }
                baze.push_back(prime[ind]);
            }
            ind++;
        }
        if(b > 1){
            baze.push_back(prime[ind]);
        }
        int ans = 0;
        for(int i = 1; i < (1<<baze.size()); i++){
            int prod = 1;
            for(int j = 0; j < baze.size(); j++){
                if(i&(1<<j)){
                    prod *= baze[j];
                }
            }
            if(__builtin_popcount(i)%2 == 1){
                ans += a/prod;
            }else{
                ans -= a/prod;
            }
        }
        fout << a-ans << "\n";
    }
    return 0;
}