//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[1000005];
vector <ll> prime;

//FUNCTIONS

ll solve (ll r, ll n){
    vector <ll> 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);

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

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

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

    return r - sum;
}

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

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

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

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

    }

    return 0;
}