#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;


int n, x, y, c, rez, div[50], sol, v[50], a, b;

void combinari(int k)
{
    int i;
    if(k == div[0]) {
        c = 0;
        sol = 1;
        for(i = 1; i <= k; ++i) {
            if(v[i] == 1) {
                ++c;
                sol *= div[i];
            }
        }
        if(c % 2 == 0)
            rez += a / sol;
        else rez -= a / sol;
    }
    else for(i = 0; i <= 1; ++i) {
        v[k + 1] = i;
        combinari(k + 1);
    }
}


void rezolva()
{
    int i, sol;
    y = b;
    x = a;
    for(i = 2; i * i <= y; ++i) {
        if(y % i == 0) {
            while(y % i == 0)
                y /= i;
            div[++div[0]] = i;
            cerr << i << ' ';
        }
    }
    if(y > 1)
        div[++div[0]] = y;
    cerr << "\n";
    combinari(0);
}


int main()
{
    int i;
    freopen ("pinex.in", "r", stdin);
    freopen ("pinex.out", "w", stdout);
    scanf("%d", &n);
    for(i = 1; i <= n; ++i) {
        rez = 0;
        div[0] = 0;
        scanf("%d %d", &a, &b);
        rezolva();
        printf("%d\n", rez);
    }
    return 0;
}