#include <cstdio>
#include <cstdlib>
#include <cstring>
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;
    int nmb = 0, ok, length;
    ll nmb1, nmb2;
    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 = 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--)
    {
              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;
              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;
}