#include <bits/stdc++.h>

using namespace std;

ifstream fin("pairs.in");ofstream fout("pairs.out");
//ifstream fin(".in");ofstream fout(".out");

#define int long long
const int SQRTB=1e6;

vector<int> lista_prime;

void Gen_Ciur()
{
    bitset<SQRTB+2> prim;
    prim[2]=1;
    for(int i=3;i<=SQRTB;i+=2)
        prim[i]=1;
    for(int i=3;i*i<=SQRTB;i++)
        if( prim[i] )
        {
            lista_prime.push_back(i);
            for(int j=i*i;j<=SQRTB;j+=2*i)
                prim[j]=0;
        }
    for(int i=2;i<=SQRTB;i++)
        if( prim[i] )
            lista_prime.push_back(i);
}

void Rez()
{
    int a,b;
    int div_b[30],ct_div=0;
    fin >> a >> b;
    for(int i=2;i<=SQRTB;i++)
        if( b%i==0 )
        {
            div_b[++ct_div]=i;
            while(b%i==0)
                b/=i;
        }
    int ans=a;
    for(int i=1;i<= (1<<ct_div)-1 ;i++)
    {
//cout << "\n" << i <<":\n";
        int val=1;
        int nr=0;
        for(int j=1; (1<<(j-1))<=i;j++)
        {
//cout << j << " ";
            if( (1<<(j-1))&i )
            {
                nr++;
                val*=div_b[j];
            }
        }
        int semn=1;
        if( nr%2==1 )semn=-1;
//        cout << val;
//        semn*=-1;
        ans+= semn*(a/val);
    }
    fout <<ans << "\n";
}

int32_t main()
{
    Gen_Ciur();
    int q;fin >> q;
    for(int i=1;i<=q;i++)
        Rez();
    fout.close();fin.close();
    return 0;
}