/*#include <iostream>
#include <fstream>

using namespace std;

fstream in("pinex.in", ios::in);
fstream out("pinex.out", ios::out);



int main()
{
	
	

    in.close();
    out.close();

	return 0;
}

*/
#include <fstream>
#include <vector>
#include <bitset>
#define pb push_back
#define szs(x) ((int)(x).size())
#define VI vector < int >
 
using namespace std;
 
const int tb = 1000003;
 
typedef long long i64;
 
VI que;
char vk[tb];
 
ifstream fin ("pinex.in");
ofstream fout ("pinex.out");
 
void ciurulika(){
    que.pb(2);
    for (int it = 3; it <= tb; it += 2)
        vk[it] = 1;
    for (int it = 3; it <= tb; it += 2){
            if (!vk[it])
              continue;
            que.pb(it);
            for (int j = (it << 1) + it; j <= tb; j += it << 1)
                vk[j] = 0;
    }
}
 
void doit (i64 A, i64 B){
    VI fakt;
    for (int it = 0; it < szs(que) && 1LL * que[it] * que[it] <= B; ++ it){
            if (B % que[it])
              continue;
            fakt.pb(que[it]);
            while (B % que[it] == 0)
                 B /= que[it];
    }
    if (B > 1)
        fakt.pb(B);
    i64 Ressit = A;
    for (int it = 1; it < (1 << szs(fakt)); ++ it){
          i64 product = 1, sub = 0;
              for (int jk = 0; jk < szs(fakt); ++ jk){
                    if ((1 << jk) & it)
                      ++ sub, product *= 1LL * fakt[jk];
              }
              sub = (sub & 1 ? -1 : 1);
              Ressit += sub * A / product;
    }
    fout << Ressit << "\n";
}
 
int main(){
    int t;
    fin >> t;
    ciurulika();
    for (; t; -- t){
            i64 x, y;
            fin >> x >> y;
            doit(x, y);
    }
 
    return 0;
}