시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 710 169 112 23.579%

문제

두 수의 최대공약수는 두 수를 나머지 없이 나눌 수 있는 가장 큰 자연수로 정의한다. 예를 들어, 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의 최대공약수를 출력한다.

예제 입력 1

3 10
10 240
12 364
100 2351
629 163547

예제 출력 1

2
240
28
1
67
W3sicHJvYmxlbV9pZCI6Ijc4MDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJHQ0QhIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI0NTAgXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWNmNVx1YzU3ZFx1YzIxOFx1YjI5NCBcdWI0NTAgXHVjMjE4XHViOTdjIFx1YjA5OFx1YmEzOFx1YzljMCBcdWM1YzZcdWM3NzQgXHViMDk4XHViMjBjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWI4NWMgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCA4XHVhY2ZjIDEyXHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWNmNVx1YzU3ZFx1YzIxOFx1YjI5NCBHQ0QoOCwxMilcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHVhY2UwLCBcdWFkZjggXHVhYzEyXHVjNzQwIDRcdWM3NzRcdWIyZTQuIDRcdWIyOTQgOFx1YWNmYyAxMlx1Yjk3YyBcdWIwOThcdWIyMGMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuICg4XHVhY2ZjIDEyXHVjNzU4IFx1YWNmNVx1YzU3ZFx1YzIxOFx1YjI5NCAxLCAyLCA0XHVhYzAwIFx1Yzc4OFx1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHVjNzkwXHVjNWYwXHVjMjE4XHVjNzU4IFx1ZDMyOVx1ZDFhMFx1YjlhY1x1YzViY1x1Yzc0MCBcdWFkZjggXHVjMjE4XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHViYWE4XHViNGUwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NTggXHVhY2YxXHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCA1XHVjNzU4IFx1ZDMyOVx1ZDFhMFx1YjlhY1x1YzViY1x1Yzc0MCA1IVx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWFjZTAgMSoyKjMqNCo1ID0gMTIwXHVjNzc0XHViMmU0LiAoMCFcdWM3NDAgMVx1Yjg1YyBcdWM4MTVcdWQ1NWNcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWMyMTggblx1YWNmYyBrXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIG4hXHVhY2ZjIGtcdWM3NTggXHVjZDVjXHViMzAwXHVhY2Y1XHVjNTdkXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBuID0gMywgayA9IDEwXHVjNzc0XHViNzdjXHViYTc0LCBHQ0QobiEsaykgPSBHQ0QoMyEsMTApID0gR0NEKDEqMiozLDEwKSA9IEdDRCg2LDEwKSA9IDJcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVhYzAxIFx1YzkwNFx1YzVkMCBuXHVhY2ZjIGtcdWFjMDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBuICZsZTsgMSwwMDAsMDAwLDAwMCwgMSAmbGU7IGsgJmxlOyAxLDAwMCwwMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWFjMDEgXHVjOTA0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgbiFcdWFjZmMga1x1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijc4MDYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHQ0QhIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgZ3JlYXRlc3QgY29tbW9uIGRpdmlzb3Igb2YgdHdvIG51bWJlcnMgaXMgZGVmaW5lZCBhcyB0aGUgbGFyZ2VzdCBpbnRlZ2VyIHRoYXQgZGl2aWRlcyBib3RoIG51bWJlcnMgd2l0aG91dCBsZWF2aW5nIGFueSByZW1pbmRlci4gRm9yIGV4YW1wbGUsIHRoZSBncmVhdGVzdCBjb21tb24gZGl2aXNvciBvZiA4IGFuZCAxMiwgd3JpdHRlbiBhcyBHQ0QoOCwxMikgaXMgNCwgYXMgNCBpcyB0aGUgbGFyZ2VzdCBpbnRlZ2VyIHRoYXQgZGl2aWRlcyBib3RoIDggYW5kIDEyICh0aGUgY29tbW9uIGRpdmlzb3JzIG9mIDggYW5kIDEyIGFyZSAxLCAyLCBhbmQgNCkuPFwvcD5cclxuXHJcbjxwPk1lYW53aGlsZSwgdGhlIGZhY3RvcmlhbCBvZiBhIG5hdHVyYWwgbnVtYmVyIGlzIHRoZSBwcm9kdWN0IG9mIGFsbCBwb3NpdGl2ZSBpbnRlZ2VycyBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gdGhhdCBudW1iZXIuIEZvciBleGFtcGxlLCB0aGUgZmFjdG9yaWFsIG9mIDUsIHdyaXR0ZW4gYXMgNSEgaXMgMSoyKjMqNCo1LCB3aGljaCBlcXVhbHMgdG8gMTIwLiBCeSBjb252ZW50aW9uLCAwISBpcyAxLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0d28gaW50ZWdlcnMsIG4gYW5kIGssIHlvdSBzaG91bGQgZmluZCB0aGUgZ3JlYXRlc3QgY29tbW9uIGRpdmlzb3Igb2YgbiEgYW5kIGsuIEZvciBleGFtcGxlLCBpZiBuID0gMyBhbmQgayA9IDEwLCB0aGVuIEdDRChuISxrKSA9IEdDRCgzISwxMCkgPSBHQ0QoMSoyKjMsMTApID0gR0NEKDYsMTApID0gMi4gV3JpdGUgYSBwcm9ncmFtIHRvIGZpbmQgdGhpcyBudW1iZXIhPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzLCBuICgwICZsdDs9IG4gJmx0Oz0gMSwwMDAsMDAwLDAwMCkgYW5kIGsgKDEgJmx0Oz0gayAmbHQ7PSAxLDAwMCwwMDAsMDAwKSByZXNwZWN0aXZlbHkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggbGluZSBvZiBpbnB1dCwgb3V0cHV0IG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIEdDRCBvZiBuISBhbmQgay48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=