37 1 s 128 MB

The greatest common divisor of two numbers is defined as the largest integer that divides both numbers without leaving any reminder. For example, the greatest common divisor of 8 and 12, written as GCD(8,12) is 4, as 4 is the largest integer that divides both 8 and 12 (the common divisors of 8 and 12 are 1, 2, and 4).

Meanwhile, the factorial of a natural number is the product of all positive integers less than or equal to that number. For example, the factorial of 5, written as 5! is 1*2*3*4*5, which equals to 120. By convention, 0! is 1.

Given two integers, *n* and *k*, you should find the greatest common divisor of *n*! and *k*. For example, if *n* = 3 and *k* = 10, then GCD(*n*!,*k*) = GCD(3!,10) = GCD(1*2*3,10) = GCD(6,10) = 2. Write a program to find this number!

Each line contains two integers, *n* (0 <= *n* <= 1,000,000,000) and *k* (1 <= *k* <= 1,000,000,000) respectively.

For each line of input, output one line containing the GCD of *n*! and *k*.

## Sample Input | ## Sample Output |
---|---|

3 10 10 240 12 364 100 2351 629 163547 | 2 240 28 1 67 |