OpenKattis
Week 4 Contest

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 -426 days 13:51:43

168:00:00

0:00:00

Problem GFactovisors

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!