10139

#include <iostream>
#include <math.h>
#include <vector>
#include <map>
#include <sstream>
#include <fstream>

#define SIZE 46500
#define lld long long
using namespace std;

// sqrt of 2^31 is ~46400
vector<int> v;
int prime[SIZE];

void PrimeGenerate()
{
    double p = sqrt(SIZE)+4;

    for(int i=3;i<p;i+=2)
    {
        if(prime[i]==0)
        {
            for(int j=i+i;j<SIZE;j+=i)
            prime[j]=1;

        }
    }
    v.clear();
    v.push_back(2);

    for(int j=3;j<SIZE;j++)
    {
       if(prime[j]==0 && j%2!=0)
       v.push_back(j);
    }

}

int main()
{
  int m,cnt;
  lld a,n;
  map<int,int> mp;
  PrimeGenerate();
  //cout<<prime[21471]<<"\n";
  //ofstream out;
  //out.open("out.txt");

  while(cin>>n)
  {
     cin>>m;
     //if(m==0 && n==0)
     //break;
     cnt=0;
     if(n>=m)
     {
        cout<<m<<" divides "<<n<<"!\n";
        //out<<m<<" divides "<<n<<"!\n";
        continue;
     }
     mp.clear();
     lld tmp = m;
     int j=0;
     int f=0;
     while(tmp>=v[j]*v[j])
     {
         if(tmp%v[j]==0)
         {
            tmp/=v[j];
            if(v[j]>n)
            {
               f=1;
               break;
            }
            mp[v[j]]++;
            cnt++;
            j=-1;
         }
         j++;
         if(j==v.size())
         break;
     }
     if(f)
     {
       //cout<<"1)\n";
       cout<<m<<" does not divide "<<n<<"!\n";
       //out<<m<<" does not divide "<<n<<"!\n";
       continue;
     }
     if(tmp>1)
     {
       if(tmp>n)
       {
         //cout<<"2)\n";
         cout<<m<<" does not divide "<<n<<"!\n";
         //out<<m<<" does not divide "<<n<<"!\n";
         continue;
       }
       mp[tmp]++;
       cnt++;
     }
     //cout<<mp.size()<<"\n";
     for(map<int,int>::iterator ii=mp.begin();ii!=mp.end();++ii)
     {
         a = 1;//ii->first;
         int t=0;//=n/a;
         int add=0;
         //cout<<t<<" "<<a<<" "<<n<<"\n";
         while(1)
         {
             a*=ii->first;
             add=n/a;
             t+=add;
             if(add==0)
             break;

         }
         if(t<ii->second)
         {
            f=1;
            break;
         }

         //cout<<ii->first<<" "<<ii->second<<"\n";
     }
     if(f)
     {
       //cout<<"3)\n";
       cout<<m<<" does not divide "<<n<<"!\n";
       //out<<m<<" does not divide "<<n<<"!\n";
     }
     else
     {
       cout<<m<<" divides "<<n<<"!\n";
       //out<<m<<" divides "<<n<<"!\n";
     }
  }
  //out.close();
  return 0;
}