#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int n, a, b, k, s, prod = 1;
int p[5000];

bool prim (int x)
{
    if (x < 2) return false;

    if (x == 2) return true;

    if (x % 2 == 0) return false;

    for (int i = 3; i * i <= x; i = i + 2)
        if (x % i == 0)
            return false;

    return true;
}

int main()
{
    in >> n;

    for (int i = 1; i <= n; i++)
    {
        in >> a >> b;

        if (b == 1)
          out << a << '\n';

        else

        {
            if (prim(b) == true)
                out << a - a / b << '\n';

            else

            {
                if (b % 2 == 0)
                {
                    k++;
                    p[k] = 2;
                    s = s + a / 2;
                    prod = prod * 2;
                }

                for (int j = 3; j <= b / 2; j = j + 2)
                {
                    if (b % j == 0 && prim(j) == true)
                    {
                        k++;
                        p[k] = j;
                        prod = prod * j;
                        s = s + a / j;
                    }
                }

                for (int j = 1; j < k; j++)
                {
                    for (int w = j + 1; w <= k; w++)
                    {
                        s = s - a / (p[j] * p[w]);
                    }
                }

                if (k > 2)
                s = s + a / prod;

                out << a - s << '\n';
            }
        }

        s = 0;
        prod = 1;
        k = 0;
    }

    return 0;
}