uva - 10139

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <climits>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>

using namespace std;

#define REP(i,n) for(__typeof(n) i=0; i<(n); i++)
#define FOR(i,a,b) for(__typeof(b) i=(a); i<=(b); i++)
#define RFOR(i,a,b) for(__typeof(b) i=(a); i>(b); i--)
#define RESET(t,value) memset((t), value, sizeof(t))
typedef long long int64;
typedef unsigned long long ui64;
typedef long double d64;
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define PI acos(-1.0)
#define INF (1<<30)
#define eps 1e-8
#define pb push_back
#define ppb pop_back
#define pii pair<double,double>
#define G struct node

template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template< class T > void setmax(T &a, T b) { if(a < b) a = b; }
template< class T > void setmin(T &a, T b) { if(b < a) a = b; }

vector < int > pset;
void initSet(int _size){ pset.resize(_size); FOR(i,0,_size-1) pset[i]=i;}
int findSet(int i){return (pset[i]== i)?i: (pset[i] = findSet(pset[i]));}
void unionSet(int i,int j){ pset[findSet(i)]=findSet(j);}
bool isSameSet(int i,int j){ return findSet(i)==findSet(j);}

#define Set(a, s) memset(a, s, sizeof (a))
#define N 50000

bool mark [N];
vector <int> primeList;

void sieve ()
{
    Set (mark, true);
    mark [0] = mark [1] = false;

    for ( int i = 4; i < N; i += 2 )
        mark [i] = false;

    for ( int i = 3; i * i <= N; i += 2 )
        if ( mark [i] )
           for ( int j = i * i; j < N; j += 2 * i )
               mark [j] = false;

    primeList.push_back (2);

    for ( int i = 3; i < N; i += 2 )
         if ( mark [i] )
            primeList.push_back (i);
}


int get_powers(int n, int p)
{
    int res = 0;
    for (int power = p ; power <= n ; power *= p)
        res += n/power;
    return res;
}

int main()
{
    sieve(); // pow(2,31) - 1
    int n,m;
    int save, count, prime;
    bool flag;
    queue < pair<int, int> > primeFact;
    while(cin>>n>>m) {
        /*
        ui64 fact = 1;
        FOR(i, 2, n) {
            fact *= (i % m);
        }
        fact %= m;
        if(!fact) cout<<m<<" divides "<<n<<"!\n";
        else cout<<m<<" does not divide "<<n<<"!\n";
        */

        if(!m) {
            cout<<m<<" does not divide "<<n<<"!\n";
            continue;
        }

        if ( n >= m ) {
            cout<<m<<" divides "<<n<<"!\n";
            continue;
        }


        save = m;
        flag = true;
        //primeFact = queue < pair<int, int> > ();



        REP(i, primeList.size()) {
            prime = primeList[i];
            if(prime > save) break;
            count = 0;
            while( !(m % prime) ) {
                count++;
                m /= prime;
            }
            if(count) {
               if( get_powers(n, prime) < count ) {
                   flag = false;
                   break;
               }
            }
            //primeFact.push(make_pair(i, count));
        }
        if( m > 50000 &&  get_powers(n, m) < 1 ) {
          flag = false;
        }

        /*
        while(!primeFact.empty()) {
            pair<int, int> p = primeFact.front();
            if( get_powers(n, p.first) >= p.second ) flag = true;
            else flag = false;
            primeFact.pop();
        }
        */
        if(flag) cout<<save<<" divides "<<n<<"!\n";
        else cout<<save<<" does not divide "<<n<<"!\n";
    }
    return 0;
}