#include <iostream>
#include <fstream>
#include <vector>
#define MAX 10000002
using namespace std;
unsigned long long m,a,b;
bool ciur[MAX];
vector<int> prime;

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

void solve(){
    fin >> a >> b;
    /// cate nr <= a sunt prime cu b ( cmmdc(val, b) = 1 )
    int ind = 0;
    vector<int> div;
    while(prime[ind]*prime[ind] <= b && ind < prime.size()){
        if(b%prime[ind] == 0){
            div.push_back(prime[ind]);
            while(b%prime[ind] == 0){
                b /= prime[ind];
            }
        }
        ind++;
    }
    if(b > 1){
        div.push_back(b);
    }
    int x = div.size();
    unsigned long long ans = 0;
    for(int i = 1; i < (1<<x); i++){
        unsigned long long subm = 1;
        for(int j = 0; j < x; j++){
            if(i&(1<<j)){
                subm *= div[j];
            }
        }
        if(__builtin_popcount(i)%2){
            ans += a/subm;
        }else{
            ans -= a/subm;
        }
    }
    fout << a-ans << "\n";
}

int main()
{
    ciur[0] = ciur[1] = 1;
    for(int i = 2; i < MAX; i++){
        if(ciur[i] == 0){
            prime.push_back(i);
            for(int j = i+i; j < MAX; j += i){
                ciur[j] = 1;
            }
        }
    }
    fin >> m;
    while(m--){
        solve();
    }
    return 0;
}