#include <iostream>
#include <fstream>

using namespace std;
using LL = long long;
const LL NMAX = 1e18;
const LL PMAX = 1e12;
const int SQRT_MAX = 1e6;
ifstream fin ( "pinex.in" );
ofstream fout ( "pinex.out" );

bool ciur[1 + SQRT_MAX];
int prime_array[1 + SQRT_MAX]; int k;
void def_prime () {
    ciur[0] = ciur[1] = true; /// composed
    for ( int i = 2; i * i <= SQRT_MAX; i ++ )
       if ( ciur[i] == false )
         for ( int j = i * i; j <= SQRT_MAX; j += i )
            ciur[j] = true;
    for ( int number = 1; number <= SQRT_MAX; number ++ )
       if ( ciur[number] == false )
         prime_array[++ k] = number;
}

LL n, p;
int prime_div[1 + SQRT_MAX]; int card;
void decompose () {
    card = 0; int index = 1;
    while ( index <= k && (long long)prime_array[index] * prime_array[index] <= p ) {
       if ( p % prime_array[index] == 0 )
         prime_div[++ card] = prime_array[index];
       while ( p % prime_array[index] == 0 )
          p /= prime_array[index];
       index ++;
    }
    if ( p > 1 )
      prime_div[++ card] = p;
}

int count_bits ( int x ) {
   int answer = 0;
   while ( x ) {
      answer ++;
      x -= (x & -x);
   }
   return answer;
}
void solve () {
    LL result = 0;
    int bit_mask = 1 << card;
    for ( int mask = 1; mask < bit_mask; mask ++ ) {
       LL answer = 1;
       for ( int bit = 0; bit < card; bit ++ )
          if ( mask & (1 << bit) )
            answer *= prime_div[1 + bit];

       int sign = count_bits ( mask );
       if ( sign % 2 == 0 )
         result -= n / answer;
       else
         result += n / answer;
    }
    fout << n - result << "\n";
}
int main()
{
   def_prime ();
   int t; fin >> t;
   while ( t -- ) {
      fin >> n >> p;
      decompose (); solve ();
   }
    return 0;
}