#include <stdio.h>
#include <vector>
#define PrimeMax 1000001
#define int64 long long int

using namespace std;

int64 PR[78510];
int64 DIV[78510];

int64 A, B, SUM, PR_S, DIV_S;
bool IN[PrimeMax];

void gen(int64 poz, int64 nr_el) {
    if (nr_el == 0) {
        int64 p = 1;
        for (int64 i = 0; i < DIV_S; i++) {
            if (IN[i] == true) {
                p *= DIV[i];          
            }
        }           
        p = A / p;
        SUM += p;
        return;
    }
    for (int64 i = poz; i <= DIV_S - nr_el; i ++) {
        IN[i] = true;
        gen(i + 1, nr_el - 1);
        IN[i] = false;
    } 
}

void get_union(int64 nr_el) {
    for (int64 i = 0; i < DIV_S; i++) {
        IN[i] = false;
    } 
    for (int64 i = 0; i <= DIV_S - nr_el; i++) {
        IN[i] = true;
        gen(i + 1, nr_el - 1);
        IN[i] = false;
    }
}

int64 solve_() {
    DIV_S = 0;
    int64 tmp = 0;
    for (int64 i = 0; PR[i] <= A && (PR[i] * PR[i]  <=  B); i++) {
        if (B % PR[i] == 0) {
            DIV[DIV_S++] = PR[i];
            while (B % PR[i] == 0) {
                B /= PR[i];      
            }
        }     
    }
    if (B != 1) {
        DIV[DIV_S++] = B;
    }
    
    for (int64 i = 1; i <= DIV_S; i++) {
        SUM = 0;
        get_union(i);
        if (i % 2 == 1) {
            tmp += SUM;
        } else {
            tmp -= SUM;       
        } 
    }
    return (A - tmp);
}

void print_(int64 R) {
    printf("%lld\n", R);      
}     
     
void read_() {
    int64 m;
    scanf("%lld", &m);
    for (int64 i = 0; i < m; i++) {
        scanf("%lld%lld", &A, &B);
        int64 R = solve_();
        print_(R);
    }         
}

void elimina(int64 nr) {
    for (int64 i = nr; i < PrimeMax; i += nr) {
        IN[i] = true;
    }     
}

void init_() {
    for (int64 i = 2; i < PrimeMax; i++) {
        if (IN[i] == false) {
            PR[PR_S++] = i;
            elimina(i);             
        }
    }      
}

int main() {
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    
    init_();
    read_();
    
    return 0;
}