#include<bits/stdc++.h>
using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

int m;
int64_t a, b;
bitset<1000005> c;
vector<int64_t> p(1, 2);

int main(){
    fin >> m;

    c[0] = c[1] = true;

    for(int i = 2; i * i <= 1000000; ++i)
        if(!c[i])
            for(int j = i * i; j <= 1000000; j += i)
                c[j] = true;

    for(int i = 3; i <= 1000000; i += 2)
        if(!c[i])
            p.push_back(i);

    for(;m--;){
        int64_t res = 0;
        fin >> a >> b;
        vector<int64_t> div;

        for(int64_t x : p){
            if(x * x > b)
                break;
            while(b % x == 0){
                div.push_back(x);
                b /= x;
            }
        }

        if(b != 1)
            div.push_back(b);

        for(int mask = 1; mask < (1 << div.size()); ++mask){
            int64_t d = 1, cnt = 0;

            for(int i = 0; (1 << i) <= mask; ++i)
                if(mask & (1 << i))
                    d *= div[i], ++cnt;

            if(cnt & 1)
                cnt = 1;
            else
                cnt = -1;

            res += cnt * a / d;
        }

        fout << a - res << '\n';
    }
}