#include <fstream>
#include <bitset>
#include <vector>

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

const int dim = 1e6;

bitset <dim+5> sieve;
vector<int> prime , v;
void Eratostene()
{
    prime.push_back(2);
   for(int i = 4 ; i <= dim ; i += 2)
        sieve[i] = true;
    for(int i = 3 ; (long long)  i <= dim ; i += 2)
        if(sieve[i] == false)
            {
                for(long long j = i * i ; j <= dim ; j += 2 * i)
                    sieve[j] = true;
            }
    for(int i = 3 ; i <= dim ; i += 2)
        if(sieve[i] == false)
            prime.push_back(i);
}

int main()
{
    Eratostene();
    unsigned int n;
    cin >> n;
    while(n--)
        {
            long long a , b;
            cin >> a >> b;
            // Descompun in factori primi
            v.clear();
            for(int i = 0 ; (long long) prime[i] * prime[i] <= b; ++i)
                {
                    if(b && b % prime[i] == 0)
                        {
                            v.push_back(prime[i]);
                            while(b % prime[i] == 0)
                                b /= prime[i];
                        }
                }
            if(b > 1)
                v.push_back(b);
            long long rasp = a;
            // Generez toate modalitatile de a alege submultimi din toti factorii primi
            for(int i = 1 ; i < (1<<(v.size())) ; ++i)
                {
                    int biti = 0;
                    unsigned long long l = 1;
                    for(int j = 0 ; j < v.size() ; ++j)
                        if(i & (1<<j))
                            {
                                 ++biti;
                                l *= v[j];
                            }
                 if(biti % 2)
                    rasp -= a/l;
                else
                    rasp += a/l;
                }
            cout << rasp << '\n';
        }
}