#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")

using namespace std;

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

const int MAX_Q = 505;
int qcnt;
long long total, sol, n, m;
long long x, e;

const int LIM = 1e6;
bitset <LIM + 5> freq;
int prim, p[100000];
int dcnt, d[100000];

void mark(int step){
    for(int i=step*step; i<=LIM; i+=step)
        freq[i] = true;
}

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    freq[0] = freq[1] = true;
    mark(2), mark(3);
    for(int i=5; i<=LIM/i; i+=6){
        if(!freq[ i ]) mark( i );
        if(!freq[i+2]) mark(i+2);
    }

    p[++prim] = 2, p[++prim] = 3;
    for(int i=5; i<=LIM; i+=6){
        if(!freq[ i ]) p[++prim] = i;
        if(!freq[i+2]) p[++prim] = i+2;
    }

    fin>>qcnt;
    while(qcnt--){
        fin>>total>>n;

        m = n, dcnt = 0;
        for(int i=1; i<=prim && p[i]<=m/p[i]; i++)
            if(m % p[i] == 0){
                d[dcnt++] = p[i];
                while(m % p[i] == 0)
                    m /= p[i];
            }
        if(m > 1)
            d[dcnt++] = m;

        sol = 0;
        for(int mask=1; mask < (1<<dcnt); mask++){
            x = 1, e = 0;
            for(int i=0; i < dcnt; i++)
                if(mask & (1 << i)){
                    x *= d[i];
                    e++;
                }

            if(e & 1)
                sol += total / x;
            else
                sol -= total / x;
        }
        fout<<total - sol<<"\n";
    }
    return 0;
}