#include <bits/stdc++.h>
#define int long long

using namespace std;

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

bool IsPrime [1000002];
vector <int> primes;

void Ciur(){
    IsPrime[0] = 0;
    IsPrime[1] = 0;
    for (int i=2;i<=1000000;++i){
        IsPrime[i] = 1;
    }
    for (int i=2;i<=1000000;++i){
        if (IsPrime[i]==1){
            for (int j=2*i;j<=1000000;j+=i){
                IsPrime[j] = 0;
            }
        }
    }
    for (int i=2;i<=1000000;++i){
        if (IsPrime[i]==1) primes.push_back(i);
    }
}


signed main()
{
    Ciur();
    int t;
    fin >> t;
    while (t--){
        int A,B;
        fin >> A >> B;
        vector <int> fct;
        int cB = B;
        for (auto x:primes){
            if (cB%x==0) fct.push_back(x);
            while (cB%x==0){
                cB /= x;
            }
        }
        if (cB>1){
            fct.push_back(cB);
        }
        int n = fct.size();
        int ans = 0;
        for (int mask=0;mask<(1<<n);++mask){
            int m_prod = 1;
            int cnt = 0;
            int val = 1;
            for (int bit=0;bit<n;++bit){
                if (mask&(1<<bit)){
                    val *= fct[bit];
                    cnt++;
                }
            }
            m_prod = A/val;
            int Ior_I = 1;
            if (cnt%2==1) Ior_I = -1;
            ans += m_prod*Ior_I;
        }
        fout << ans << '\n';
    }
    return 0;
}