#include <iostream>

#include <vector>

#include <cstring>

#include <cstdio>

using namespace std;

const int MAXN=;

bool vis[MAXN+];

int prime[MAXN+];

int n,m,p;

vector<pair<int,int> > exp;

void init()//素数筛选

{

    memset(vis,,sizeof(vis));

    p=;

    for(int i=; i<=MAXN; ++i)

    {

        if(vis[i]==false)

            prime[p++]=i;

        for(int j=; j<p&&i*prime[j]<=MAXN; ++j)

            vis[i*prime[j]]=true;

    }

}

bool check(int x,int y)//判断当前的素数，n是否有这么多个

{

    int tmp=n,sum=;

    while(tmp)

    {

        sum+=tmp/x;

        tmp/=x;

    }

    return y<=sum;

}

bool judge()

{

    for(int i=; i<exp.size(); ++i)

        if(!check(exp[i].first,exp[i].second))

            return false;

    return true;

}

int main()

{

    init();

    while(scanf("%d%d",&n,&m)==)

    {

        if(m==)

        {

            printf("%d does not divide %d!\n",m,n);

            continue;

        }

        exp.clear();

        int t=m;

        for(int i=; i<p&&prime[i]<=m; ++i)

            if(m%prime[i]==)

            {

                int cnt=;

                while(m%prime[i]==)

                {

                    m/=prime[i];

                    ++cnt;

                }

                exp.push_back(make_pair(prime[i],cnt));//m的素数个数与m的素数因子对应

            }

        if(m!=)

            exp.push_back(make_pair(m,));

        if(judge())

            printf("%d divides %d!\n",t,n);

        else

            printf("%d does not divide %d!\n",t,n);

    }

    return ;

}