#include <iostream>
#include <fstream>
    
using namespace std;
using ll = long long;

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

const int nmax = 1e6;
const int kmax = 999000;

int n, k, divs[kmax + 5];
ll x, y;
bool v[nmax+5];

/* 1 <= y <= 10^12

10^12-nek legnagyobb osztoja sqrt(10^12) = 10^6 lehet, tehat az osszes primszamot 
megkeressuk addig.

*/

void debug(){
    cout << "DEBUG" << '\n';
}

void solve(){
    fin >> x >> y;
    ll s1 = 0, s2 = 0, s3 = 0, p = 1;
    for(int i = 0; i < k && divs[i] <= y; i++)
        if(y % divs[i] == 0)
            s1 += (x / divs[i]);

    for(int i = 0; i < k-1 && divs[i] <= y; i++)
        if(y % divs[i] == 0) // divs[i] egy prim osztoja y-nak
            for(int j = i+1; j < k && divs[j] <= y; j++)
                if(y % divs[j] == 0) // divs[j] is prim oszto
                    s2 += (x / (divs[i] * divs[j]));
    for (int i = 0; i < k-2 && divs[i] <= y; i++) {
        if (y % divs[i] == 0) {
            for (int j = i+1; j < k-1 && divs[j] <= y; j++) {
                if (y % divs[j] == 0) {
                    for (int z = j+1; z < k && divs[z] <= y; z++) {
                        if (y % divs[z] == 0) {
                            s3 += (x / (divs[i] * divs[j] * divs[z]));
                        }
                    }
                }
            }
        }
    }

        
    int cnt = 0;
    for(int i = 0; i < k && divs[i] <= y; i++)
        if(y % divs[i] == 0)
            p *= divs[i], cnt++;
    
    //s3 = x / p;

    ll sum = 0;
    if(cnt == 1)
        sum = s1;
    else if(cnt == 2)
        sum = s1 - s2;
    else
        sum = s1 - s2 + s3;

    fout << x - sum << '\n';
}

void precompute(){
    v[0] = 1;
    v[1] = 1;
    for(int i = 2; i*i <= nmax; i++)
        if(v[i] == 0)
            for(int j = i*i; j <= nmax; j += i)
                v[j] = 1;
    k = 0;
    for(int i = 2; i <= nmax; i++)
        if(v[i] == 0)
            divs[k++] = i;
}

int main()
{
    fin >> n;
    precompute();
    while(n--)
        solve();
    
    return 0;
}