#include<algorithm>
#include<bitset>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<fstream>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;

#ifdef HOME
const string inputFile = "input.txt";
const string outputFile = "output.txt";
#else
const string problemName = "pinex";
const string inputFile = problemName + ".in";
const string outputFile = problemName + ".out";
#endif

typedef long long int lld;

int N, T;
lld A, B, sol;
bitset < 500000 + 20 > viz;
int P[100000], top;
lld Q[20];
int S[20];

void ciur() {
    int i, j;

    P[++top] = 2;

    for(i = 3; i * i <= 1000000; i += 2)
        if(!viz[i / 2]) {
            P[++top] = i;
            for(j = i * i; j <= 1000000; j += 2 * i)
                viz[j / 2] = 1;
        }

    for(; i <= 1000000; i += 2)
        if(!viz[i / 2])
            P[++top] = i;
}

void desc(int x, lld *Q, int &cnt) {
    int i;

    cnt = 0;

    for(i = 1; P[i]*P[i] <= x && i <= top; i++)
        if(x % P[i] == 0) {
            Q[++cnt] = P[i];
            while(x % P[i] == 0)
                x /= P[i];
        }

    if(x > 1)
        Q[++cnt] = x;
}

void back(int top, int sign, lld num) {
    if(top > T + 1)
        return;

    sol += sign * A / num;

    for(int i = S[top - 1] + 1; i <= T; i++) {
        S[top] = i;
        back(top + 1, -sign, num * Q[i]);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen(inputFile.c_str(), "r", stdin);
    freopen(outputFile.c_str(), "w", stdout);
#endif

    scanf("%d", &N);

    ciur();

    while(N--) {
        scanf("%lld%lld", &A, &B);

        sol = 0;
        T = 0;

        desc(B, Q, T);

        back(1, 1, 1);

        printf("%lld\n", sol);
    }

    return 0;
}