#include <cstdio>

#include <cstring>

using namespace std;

FILE *f, *g;

long long a, b;

bool p[1000001];
long long pr[80000], kp;
long long desc[101], k;

void ciur()
{
    int i, j, n = 1000000;

    p[0] = p[1] = 1;

    for(i = 4; i <= n; i += 2)
        p[i] = 1;

    for(i = 3; i * i <= n; i += 2)
    {
        if(p[i] == 0)
        {
            for(j = i * i; j <= n; j += i * 2)
                p[j] = 1;
        }
    }

    pr[++ kp] = 2;

    for(i = 3; i <= n; i += 2)
    {
        if(p[i] == 0)
            pr[++ kp] = i;
    }
}

void descom(long long b)
{
    int d = 1, p = 0;

    k = 0;
    memset(desc, 0, sizeof(desc));

    while(b % pr[d] == 0)
        p ++, b /= pr[d];

    if(p > 0)
        desc[++ k] = 2;

    while((d <= kp) && pr[d] * pr[d] <= b)
    {
        p = 0;

        while(b % pr[d] == 0)
            p ++, b /= pr[d];

        if(p > 0)
            desc[++ k] = pr[d];


        d ++;
    }

    if(b > 1)
        desc[++ k] = b;
}

void solve()
{
    descom(b);

    int i, j;

    long long rez = a;
    long long sign = 1, prod = 1;
    for(i = 1; i < (1 << k); i ++)
    {
        long long sign = 0, prod = 1;

        for(j = 0; j < k; j ++)
        {
            if((i & (1 << j)) != 0)
            {
                prod *= desc[j + 1];

                sign ++;
            }
        }

        if(sign % 2 == 1)
            sign = 1;

        else
            sign = -1;

        rez -= sign * a / prod;
    }

    fprintf(g, "%lld\n", rez);
}

void readFile()
{
    f = fopen("pinex.in", "r");
    g = fopen("pinex.out", "w");

    int t;
    fscanf(f, "%d", &t);

    int i;
    for(i = 1; i <= t; i ++)
    {
        fscanf(f, "%lld%lld", &a, &b);

        solve();
    }

    fclose(f);
    fclose(g);
}

int main()
{
    ciur();

    readFile();

    return 0;
}