#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const string filename = "pinex";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

const int maxN = 1000005;
long long a, b, prime[55], ans;
vector <int> prim;
int marcat[maxN];

void ciur()
{
    for(int i = 2; i <= maxN; i++)
    {
        if(!marcat[i])
        {
            for(int j = 2 * i; j <= maxN; j += i)
                marcat[j] = 1;
            prim.push_back(i);
        }
    }
}

void solve()
{
    fin >> a >> b;
    int total_prime = 0;
    for(int i = 0; prim[i] * prim[i] <= b; i++)
    {
        if(b % prim[i] != 0)
            continue;
        prime[++total_prime] = prim[i];
        while(b % prim[i] == 0)
            b /= prim[i];
    }
    if(b > 1)
        prime[++total_prime] = b;
    ans = 0;
    for(long long config = 1; config <= (1 << total_prime) - 1; config++)
    {
        int nr = 0, semn = 1;
        long long p = 1;
        for(int i = 0; i < total_prime; i++)
        {
            if((1 << i) & config)
            {
                nr++;
                p *= prime[i + 1];
            }
        }
        if(nr % 2 == 0)
            semn = -1;
        ans += 1LL * semn * (a / p);
    }
    fout << a - ans << '\n';
}

int main()
{
    int nr_teste;
    fin >> nr_teste;
    ciur();
    while(nr_teste--)
        solve();
    return 0;
}