#include <cstdio>
#include <cstdlib>
using namespace std;


#define ll long long
#define max_p 1000005

bool prim[max_p];
int m, l, h;
ll v[81000], fprim[40];

void fact(long long n)
{
     int i = 1, c;
     while(n > 1)
     {
             if(v[i] * v[i] > n) break;
             c = 0;
             while(!(n % v[i]))
             {
                  c++;
                  n /= v[i];
             }
             if(c) fprim[++l] = v[i];
             i++;
     }
     if(n > 1) fprim[++l] = n;
}

int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    int i, j, c = 0;
    ll p, A, B;
    scanf("%i", &m);
    for(i = 2; i < max_p; i++)
    {
          if(!prim[i])
          {
                      v[++h] = i;
                      for(j = i + i; j < max_p; j += i) prim[j] = 1;
          }
    }
    while(m--)
    {
              scanf("%lld %lld", &A, &B);
              l = 0;
              fact(B);
              ll sol = A;
              for(i = 1; i < (1 << l); i++)
              {
                    p = 1;
                    c = 0;
                    for(j = 0; j < l; j++)
                    {
                          if(i & (1 << j))
                          {
                               c++;
                               p *= fprim[j + 1];
                          }
                    }
                    if(c & 1) p = -p;
                    sol += A / p;
              }
              printf("%lld\n", sol);
    }
    return 0;
}