#include <cstdio>
#include <cmath>
using namespace std;
bool ciur[1000005];
int prime[100005], div[15], k;
void form_prime(long long n){
    int i, j, rad;
    k = 1; prime[1] = 2;
    rad = sqrt(n);
    for (i = 3; i <= rad; i += 2)
        if (!ciur[i]){
            prime[++k] = i;
            for (j = i * i; j <= n; j += 2 * i)
                ciur[j] = 1;
        }
}
int divizori(long long n){
    int d, nrdiv = 0;
    for (d = 1; prime[d] * prime[d] <= n && d <= k; d ++){
        if (n % prime[d] == 0){
            div[++nrdiv] = prime[d];
            while (n % prime[d] == 0)
                n /= prime[d];
        }
    }
    if (n > 1)
        div[++nrdiv] = n;
    return nrdiv;
}
long long submultimi(int n, long long a){
    int i, j, card;
    long long ns, prod, ans = a;
    ns = (1 << n) - 1;
    for (i = 1; i <= ns; i ++){
        card = 0;
        prod = 1;
        for (j = 0; j < n; j ++)
            if ((1 << j) & i){
                prod = 1LL * prod * div[j + 1];
                card ++;
            }
        if (card & 1)
            ans -= a / prod;
        else
            ans += a / prod;
    }
    return ans;
}
int main(){
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    int t, i;
    long long a, b;
    form_prime(1000000);
    scanf("%d", &t);
    for (i = 1; i <= t; i ++){
        scanf("%lld%lld", &a, &b);
        printf("%lld\n", submultimi(divizori(b), a));
    }
    return 0;
}