#include <bits/stdc++.h>
#define cin ci
#define cout co
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
int m, a, n;
int main()
{
    cin >> m;
    while(m--)
    {
        cin >> a >> n;
        vector<int> div;
       // div.push_back(0);
        for(int d=2; d*d<=n; d++)
            if(n % d == 0)
            {
                div.push_back(d);
                while(n % d == 0)
                    n /= d;
            }
        if(n > 1)
            div.push_back(n);
        int sum = 0;
        for(int mask = 1; mask < (1 << (div.size())); mask++)
        {
            int bits = 0, mult = 1;
            for(int i=0; i<div.size(); i++)
                if(mask & (1 << i))
                {
                    bits++;
                    mult *= div[i];
                }
            int cur = a / mult;
            if(bits % 2 == 1)
                sum += cur;
            else
                sum -= cur;
        }
        cout << a - sum << '\n';


    }
    return 0;
}