#include <bits/stdc++.h>

using namespace std;
vector <long long> primes;
vector <long long> v;
const long long N = 1e6;
bitset <N> b;
void ciur(){
    for(long long i = 2;i * i <= N;i++){
        if(!b[i])
        for(long long j = i * i;j <= N;j+=i){
            b[j] = true;
        }
    }
    for(long long i = 2;i <= N;i++)
        if(!b[i])
           primes.push_back(i);
}
int main()
{
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");
    ciur();
    long long m;
    cin >> m;
    while(m--){
        long long a,b;
        cin >> a >> b;
        v.clear();
        for(auto x : primes){
            if(b % x == 0){
                v.push_back(x);
            }
        }
        long long rez = 0;
        for(long long i = 1;i < (1 << v.size());i++){
            long long nr_bits = 0, p = 1;
            for(long long j = 0;j < v.size();j++){
                if(i & (1 << j)){
                    nr_bits++;
                    p *= v[j];
                }
            }
            if(nr_bits % 2 == 0){
                rez -= (a / p);
            }else{
                rez += (a / p);
            }
        }
        cout << a - rez << "\n";
    }
    return 0;
}