#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;


#define ll long long
#define max_p 1000000

ll M, A, B, fact[30];
int fprim[80000];
bool prim[max_p];


void sieve()
{
     fill(prim + 2, prim + max_p, true);
     for(int i = 2; i < max_p; i++)
     {
             if(prim[i])
             {
                        fprim[++fprim[0]] = i;
                        for(int j = i + i; j < max_p; j += i) prim[j] = false;
             }
     }
}

void solve()
{
     ll d = 0, t = 0;
     while(B > 1)
     {
             ++d;
             if(B % fprim[d] == 0)
             {
                  fact[++t] = fprim[d];
                  while(B % fprim[d] == 0) B /= fprim[d];
             }
             if(fprim[d] * fprim[d] > B && B > 1)
             {
                         fact[++t] = B;
                         B = 1;
             }
     }
     ll sol = A;
     for(int i = 1; i < (1 << t); i++)
     {
             ll prod = 1, nr = 0;
             for(int j = 0; j < t; j++)
             {
                     if(i & (1 << j))
                     {
                          prod = 1LL * prod * fact[j + 1];
                          nr++;
                     }
             }
             if(nr % 2) nr = -1;
             else nr = 1;
             sol += 1LL * nr * A / prod;
     }
     cout << sol << "\n";
}

int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    int i;
    sieve();
    cin >> M;
    for(i = 0; i < M; i++)
    {
          cin >> A >> B;
          solve();
    }
    return 0;
}