#include <fstream>
using namespace std;

ifstream cin ("zero2.in");
ofstream cout ("zero2.out");

int main ()
{
    for (int indice = 1 , lungime , baza ; indice <= 10 ; indice++)
    {
        cin >> lungime >> baza;

        int ultimul = 0 , exponent_ultim = 0;
        for (int factor = 2 ; factor * factor <= baza ; factor++)
            if (baza % factor == 0) {
                ultimul = factor;
                exponent_ultim = 0;
                while (baza % factor == 0) {
                    baza /= factor;
                    exponent_ultim++;
                }
            }

        if (baza > 1) {
            ultimul = baza;
            exponent_ultim = 1;
        }
        
        unsigned long long zero = 0;
        for (long long impartitor = ultimul ; impartitor <= lungime ; impartitor *= ultimul)
            zero += impartitor / ultimul * (lungime - impartitor + 1);

        cout << zero / exponent_ultim << '\n';
    }

    cout.close(); cin.close();
    return 0;
}