//ALEXANDRU MICLEA
 
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>
#include <assert.h>
 
using namespace std;
using ll = long long;
 
#include <fstream>
//ifstream cin("input.in"); ofstream cout("output.out");
ifstream cin("pinex.in"); ofstream cout("pinex.out");
 
//VARIABLES

int ciur[100005];
vector <int> prime;

//FUNCTIONS

ll solve (ll r, ll n){
    vector <int> p;

    for (auto& i : prime){
        if (n % i == 0){
            p.push_back(i);
            while (n % i == 0){
                n /= i;
            }
        }
    }
    if (n > 1) p.push_back(n);

    int sum = 0;
    for (int msk = 1; msk < (1 << p.size()); msk++){
        int mult = 1, bits = 0;

        for (int i = 0; i < (int) p.size(); i++){
            if (msk & (1 << i)){
                bits++;
                mult *= p[i];
            }
        }

        int cur = r / mult;
        if (bits % 2) sum += cur;
        else sum -= cur;
    }

    return r - sum;
}

//MAIN
 
int main() {
    
    int q; cin >> q;

    for (int i = 2; i * i<= 100004; i++){
        if (!ciur[i]) prime.push_back(i);
        for (int j = i; j <= 100004; j += i){
            ciur[i] = 1;
        }
    }



    while (q--){
        ll a, b; cin >> a >> b;

        cout << solve (a, b) << '\n';

    }

    return 0;
}