/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, OCaml, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
int di[10000];


int termeni(long long a,long long b){
     
     long long total=0;
     int nr=1,pos=0;
     while(b>1 && nr * nr <= b){
         nr++;
         if(b%nr==0 and nr<a){
             di[pos] = nr;
             pos++;
            while(b%nr==0)
                b/=nr;
         }
        //  if(nr * nr > b) {
        //      if(b != 1) {
        //          di[pos] = b;
        //          pos++;
        //      }
        //  }
    }
    if(b > 1) {
        di[pos] = b;
        pos++;
    }
    for(int i = 1;i<(1<<pos);i++){
        int p=1, cnt=0;
        
        for(int j=0;(1<<j)<=i;j++){
            if((i & (1<<j))!=0){
                p*=di[j];
                cnt++;
            }
        }
       
        if(cnt%2)
        total+=a/p;
        else
        total-=a/p;
    }
    return a - total;
}

int main()
{
   long long n;
   cin>>n;
   for(int i =0;i<n;i++){
       int a,b;
       cin>>a>>b;
       cout<<termeni(a,b)<<endl;
   }
}