Felix Halim .NET  
Google 

ACM/ICPC Indonesia National Contest 2007

Problem B

GCD!

Time Limit: 1s


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!

Input

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

Output

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

Sample Input

3 10
10 240
12 364
100 2351
629 163547

Sample Output

2
240
28
1
67


Problem Setter: Suhendry Effendy


Kembali ke pembahasan soal ini

Lihat problem lain:

  1. Minimum Swap
  2. GCD!
  3. Playing With Domino
  4. Email from the Professor
  5. Panda Number
  6. Jakarta Traffic Jam
  7. Sultan's Land
  8. Tree Median


© Felix Halim 2009 (Loaded in 0.00196 secs)