#include <iostream>
#include <fstream>
#include <map>

using namespace std;

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

int prim[1000005] , n , d[1000005] , cnt , k , j , t , a , b;

void ciur ()
{
    for (int i = 2 ; i <= 1000000 ; i++)
    {
        if (prim[i] == 0)
        {
            d[++cnt] = i;
           for (int j = 2 * i ; j <= 1000000 ; j = j + i)
           {
               prim[j] = 1;
           }
        }
    }
}

int solve (int a , int b)
{
    int ok = 0 , cnt = 0;;
    map <long long , int >m;
    for (k = 1 ; d[k] <= a ; k++)
    {
        ok = 0;
        while (b % d[k] == 0)

            b = b / d[k] , ok = 1;
        if (ok == 1)
        {
            int aux = d[k];
            for (j = aux ; j <= a ; j = j + aux)
            {
                if (m[j] == 0)
                    cnt++ , m[j] = 1;
            }
        }
    }
    return a - cnt;
}


int main()
{
    ciur ();
    f >> t;
    while (t)
    {
        f >> a >> b;
        g << solve (a , b) << '\n';
        t--;
    }
    return 0;
}