#include <bits/stdc++.h>

using namespace std;

const int MAXRB = 1e6 , MAXLEN = 78498 , MAXF = 11;
bitset < MAXRB + 1 > ciur;
int pr[MAXLEN + 1] , lenf;
long long fb[MAXF] , a;
long long bkt ( int i , int l , long long p ) {
    if ( i == lenf ) {
        if ( p != 1 ) {
            if ( l % 2 == 1 )
                return a / p;
            return -( a / p );
        }
        return 0;
    }
    return bkt ( i + 1 , l , p ) + bkt ( i + 1 , l + 1 , p * fb[i] );
}
int main () {
    ifstream fin ( "pinex.in" );
    ofstream fout ( "pinex.out" );
    int i , j , lenp , m;
    long long b;

    for ( i = 2 ; i * i <= MAXRB ; i++ )
        if ( ciur[i] == 0 )
            for ( j = i * i ; j <= MAXRB ; j = j + i )
                ciur[j] = 1;
    lenp = 0;
    for ( i = 2 ; i <= MAXRB ; i++ )
        if ( ciur[i] == 0 ) {
            pr[lenp] = i;
            lenp++;
        }
    pr[lenp] = MAXRB + 1;

    fin >> m;
    for ( i = 0 ; i < m ; i++ ) {
        fin >> a >> b;
        j = lenf = 0;
        while ( ( long long ) pr[j] * pr[j] <= b ) {
            if ( b % pr[j] == 0 ) {
                b = b / pr[j];
                fb[lenf] = pr[j];
                lenf++;
                while ( b % pr[j] == 0 )
                    b = b / pr[j];
            }
            j++;
        }
        if ( b > 1 ) {
            fb[lenf] = b;
            lenf++;
        }
        fout << a - bkt ( 0 , 0 , 1 ) << '\n';
    }
    return 0;
}