#include <bits/stdc++.h>
#define DIM 1001
#define MOD 666013
#define y1 eiurhfef

using namespace std;

ifstream fin("pinex.in");

ofstream fout("pinex.out");

vector <int> v;

int answer, value, Q, a, b;

void get_prime_divi(int n){

    int d = 2;

    while(n > 1){

        if(n % d == 0){

            v.push_back(d);

            while(n % d == 0)

                n /= d;

        }

        if(d >= 3)

            d += 2;

        else d++;

        if(d * d > n && n > 1)

            d = n;

    }

}

int solve(int a, int b){

    v.clear();

    get_prime_divi(b);

    answer = 0;

    for(int k = 1 ; k < (1LL << v.size()) ; k++){

        value = 1;

        for(int i = 0 ; i < v.size() ; i++)

            if(((k >> i) & 1) == 1)

                value *= v[i];

        if(__builtin_popcount(k) % 2 == 1)

            answer += a / value;

        else answer -= a / value;

    }

    return answer;


}

int main(){

    fin >> Q;

    while(Q--){

        fin >> a >> b;

        fout << a - solve(a, b) << "\n";

    }

}