#include <iostream>
#include <fstream>
using namespace std;
ifstream f ( "zero2.in" );
ofstream g ( "zero2.out" );
const int Q = 10;
const unsigned long long MAX = 9223372036854775807;
struct factexp
{
    long long fact, exp;
};
void desc ( long long x, factexp v[], long long int &lv )
{
    lv = 0;

    if ( x % 2 == 0 )
    {
        v[++lv].exp = 0;
        v[lv].fact = 2;

        while ( x % 2 == 0 )
        {
            x /= 2;
            v[lv].exp++;
        }
    }

    for ( int i = 3; i * i <= x; i += 2 )
        if ( x % i == 0 )
        {
            v[++lv].exp = 0;
            v[lv].fact = i;

            while ( x % i == 0 )
            {
                x /= i;
                v[lv].exp++;
            }
        }

    if ( x > 1 )
    {
        v[++lv].fact = x;
        v[lv].exp = 1;
    }
}
int main()
{
    long long N, B, T = Q;

    while ( T-- )
    {
        f >> N >> B;
        long long int lv;
        factexp v[30];
        desc ( B, v, lv );
        long long mn = MAX;

        for ( int i = 1; i <= lv; i++ )
        {
            long long p = v[i].fact;
            long long x = 0;
            long long k = N / p;

            for ( long long int j = 1; k != 0; j++ )
            {
                k = N / p;
                x += ( N + 1 ) * k - ( ( k + 1 ) * p * k ) / 2;
                p *= v[i].fact;
            }

            x /= v[i].exp;

            ///cout<<v[i].gst<<'\n';
            if ( x < mn )
                mn = x;
        }

        g << mn << '\n';
    }

    return 0;
}