Start

2016-09-22 21:30 CEST

Week 4 Contest

End

2016-09-29 21:30 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -364 days 1:52:53

Time elapsed

168:00:00

Time remaining

0:00:00

Problem G
Factovisors

The factorial function, $n!$ is defined thus for $n$ a non-negative integer:

\[ n! = \begin{cases} 1 & \text {if $n = 0$} \\ n \cdot (n-1)! & \text {if $n > 0$} \end{cases} \]

We say that $a$ divides $b$ if there exists an integer $k$ such that $k \cdot a = b$.

Input

The input to your program consists of several lines, each containing two non-negative integers, $n$ and $m$, both less than $2^{31}$.

Output

For each input line, output a line stating whether or not $m$ divides $n!$, in the format shown below.

Sample Input 1 Sample Output 1
6 9
6 27
20 10000
20 100000
1000 1009
9 divides 6!
27 does not divide 6!
10000 divides 20!
100000 does not divide 20!
1009 does not divide 1000!