시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 455 108 69 22.697%

문제

두 수의 최대공약수는 두 수를 나머지 없이 나눌 수 있는 가장 큰 자연수로 정의한다. 예를 들어, 8과 12의 최대공약수는 GCD(8,12)로 나타내고, 그 값은 4이다. 4는 8과 12를 나눌 수 있는 가장 큰 정수이기 때문이다. (8과 12의 공약수는 1, 2, 4가 있다)

자연수의 팩토리얼은 그 수보다 작거나 같은 모든 양의 정수의 곱이다. 예를 들어, 5의 팩토리얼은 5!로 나타내고 1*2*3*4*5 = 120이다. (0!은 1로 정한다)

두 수 n과 k가 주어졌을 때, n!과 k의 최대공약수를 구하는 프로그램을 작성하시오. 예를 들어, n = 3, k = 10이라면, GCD(n!,k) = GCD(3!,10) = GCD(1*2*3,10) = GCD(6,10) = 2가 된다.

입력

각 줄에 n과 k가 하나씩 주어진다. (0 ≤ n ≤ 1,000,000,000, 1 ≤ k ≤ 1,000,000,000)

출력

입력의 각 줄에 대해서, n!과 k의 최대공약수를 출력한다.

예제 입력

3 10
10 240
12 364
100 2351
629 163547

예제 출력

2
240
28
1
67

힌트