#include <fstream>
#include <vector>

using namespace std;

ifstream cin("pinex.in");
ofstream cout("pinex.out");

int q;

void read() {
    cin>>q;
}

int cmmdc(int a,int b) {
    int mod;
    while(a) {
        mod=a%b;
        a=b;
        b=mod;
    }
    return b;
}

void solve() {
    int a,b;
    while(q--) {
        cin>>a>>b;
        int cnt=0;
        for(int i=1;i<=a;i++) {
            if(cmmdc(b,i)>1) {
                cnt++;
            }
        }
        cout<<a-cnt<<"\n";
    }
}

int main() {
 
    read();
    solve();
    return 0;
}