#include <fstream>
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
long long prime[77003];
int main() {
        long long n,a,b,k;
        cin>>n;
        for(int i=1; i<=n; i++) {
                cin>>a>>b;
                k = 0;
                for(int j = 2; j * j <= b; j++) {
                        if(b % j == 0) {
                                prime[k] = j;
                                k++;
                        }
                        while(b % j == 0)
                                b /= j;
                }
                if(b > 1) {
                        prime[k] = b;
                        k++;
                }
                int ans = 0;
                for(int mask = 0; mask < (1 << k); mask++) {
                        long long cnt = 0,prod = 1;
                        for(int j = 0; j < k; j++) {
                                if((1 << j) & mask) {
                                        cnt++;
                                        prod *=  prime[j];
                                }
                        }
                        //cout<<mask<<" "<<ans<<" "<<prod<<'\n';
                        ans += ((cnt & 1) ? -1 : 1) * (a / prod);
                }
                cout<< ans <<'\n';
        }
        return 0;
}