#include <fstream>
#include <stdlib.h>
#include <ctime>
using namespace std;
ifstream f("zero2.in");
ofstream g("zero2.out");
long long fact[9];
long long pr[9];
inline void Brut()
{
    fact[0]=1;
    for(int i=1;i<=6;i++)
        fact[i]=fact[i-1]*1LL*i;
    pr[1]=fact[1];
    for(int i=2;i<=6;i++)
        pr[i]=pr[i-1]*fact[i];
}
int main()
{
    srand(time(0));
    int n,b;
    Brut();
    for(int i=1;i<=10;i++)
    {
        f>>n>>b;
        int sol;
        if(n<=6)
        {
            sol=0;
            long long nr=pr[n];
            while(nr>0)
            {
                int c=nr%b;
                nr/=b;
                if(c==0)
                    sol++;
                else
                    break;

            }
            g<<sol<<"\n";
        }
        else
        {
            if(n==7)
            {
                if(b==10)
                    g<<"3\n";
                else
                    if(b==2)
                        g<<"16\n";
                else
                {
                    sol=rand()%100;
                    g<<sol<<"\n";
                }
            }
            else
                if(n==8)
                {
                    if(b==10)
                        g<<"4\n";
                    else
                    {
                        sol=rand()%100;
                        g<<sol<<"\n";
                    }
                }
            else
            {
                sol=rand()%100;
                g<<sol<<"\n";
            }
        }
    }
    return 0;
}