//#include <fstream>
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;


#define ll long long
#define max_p 1000005

ll i, j, n, B, M, k, A;
int fprim[7330000], fact[6330000];
bool prim[1000005];

//ifstream in("pinex.in");
//ofstream out("pinex.out");

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

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

int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    int i, j;
    sieve();
    int nmb = 0, length, nmb1, nmb2, ok;
    char s[40];
    fgets(s, 40, stdin);
    length = strlen(s) - 1;
    for(i = 0; i < length; i++) nmb = nmb * 10 + s[i] - '0';
    M = nmb;
    for(i = 0; i < M; i++)
    {
          fgets(s, 40, stdin);
          length = strlen(s) - 1;
          nmb1 = 0, nmb2 = 0, ok = 0;
          for(j = 0; j < length; j++)
          {
                if(s[j] == ' ') ok = 1;
                else if(ok) nmb2 = nmb2 * 10 + s[j] - '0'; else nmb1 = nmb1 * 10 + s[j] - '0';
          }
          A = nmb1;
          B = nmb2;
          solve();
    }
    return 0;
}