#include <iostream>
#include <fstream>

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

long long v[10001];
const int N = 1e6;
char ciur[N + 1];
int primes[79000], firstPrime[N + 1], cnt;

int divizori_primi(long long b)
{
    long long i = 2;
    int noDiv = 0;
    while(b * 1LL > N && i * i <= b){
        if(!(b % i)){
            v[++noDiv] = i;
            while(!(b % i)) b /= i;
        }
        i++;
    }
    /// b; b = b + 1
    /// ++b; b = b + 1
    if(b * 1LL <= N){ /// if B can be further decomposed based on firstPrime array
        while(b > 1){
            v[++noDiv] = firstPrime[b];
            int div = firstPrime[b];
            while(!(b % div)) b /= div;
        }
    } else
        if(b > 1)
            v[++noDiv] = b;
    return noDiv;
}

void preCompute(){
    for(int i = 2; i * i <= N; i++)
        if(!ciur[i]){
            firstPrime[i] = i;
            for(int j = i * i; j <= N; j += i){
                ciur[j] = 1;
                firstPrime[j] = i;
            }
        }
    for(int i = 2; i <= N; i++)
        if(!ciur[i]) {
            primes[++cnt] = i;
            firstPrime[i] = i;
        }
}

int main()
{
    int m, i, j, q;
    long long a, b;
    preCompute();
    f >> m;
    for( i = 1; i <= m; i++ )
    {
        f >> a >> b;
        int nrdiv = divizori_primi(b);
        long long sum=0;
        int k = (1 << nrdiv);
        for( j = 1; j < k; j++ )
        {
            int par = 0;
            for ( q = 0; q < nrdiv; q++ )
                par += (j >> q) & 1;
            long long x = 1;
            for ( q = 0; q < nrdiv; q++ )
                if ((j >> q) & 1)
                    x *= v[q+1];
            if( par & 1 )
                sum += a/x;
            else sum -= a/x;
        }
        g << a - sum << '\n';
    }
    return 0;
}