#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
bool mark[2000000];
vector<ll>isprime;


void sieve()
{
    mark[0]=true;
    mark[1]=true;
    for(ll i=2; i*i<=1000005; i++)
    {
        if(mark[i]==false)
        {
            for(ll j=i*i; j<=1000005; j+=i)
            {
                mark[j]=true;
            }
        }
    }
    for(ll i=2;i<1000005;i++)
    {
        if(mark[i]==false)
            isprime.push_back(i);
    }
}



bool factor(ll n,ll m)
{
    ll a,b,c,d,i,j,k;
    a=sqrt(m);
    vector< pair<ll,ll> >v;
    for(i=0; i<isprime.size(); i++)
    {
        if(isprime[i]>a)
            break;
        if(m%isprime[i]==0)
        {
            ll cnt=0;
            while(m%isprime[i]==0)
            {
                m/=isprime[i];
                cnt++;
            }
            v.push_back(make_pair(isprime[i],cnt));
        }
    }
    if(m>1)
        v.push_back(make_pair(m,1));


    for(auto t: v)
    {
        c=n;
        ll cnt=0;
        while(c)
        {
            c/=t.first;
            cnt+=c;
        }
        if(cnt<t.second)
            return false;
    }
    return true;
}



int main()
{
    sieve();
    ll n,m,i,j,k;
    while(cin>>n>>m)
    {
        if(factor(n,m)==true)
            cout<<m<<" divides "<<n<<"!"<<endl;
        else
            cout<<m<<" does not divide "<<n<<"!"<<endl;
    }
    return 0;
}