Least common multiple

Time Limit: 1000ms
Memory Limit: 65536KB
This problem will be judged on HDU. Original ID: 3092
64-bit integer IO format: %I64d      Java class name: Main

Description

Partychen like to do mathematical problems. One day, when he was doing on a least common multiple(LCM) problem, he suddenly thought of a very interesting question: if given a number of S, and we divided S into some numbers , then what is the largest LCM of these numbers? partychen thought this problems for a long time but with no result, so he turned to you for help!
Since the answer can very big,you should give the answer modulo M.

Input

There are many groups of test case.On each test case only two integers S( 0 < S <= 3000) and M( 2<=M<=10000) as mentioned above.

Output

Output the largest LCM modulo M of given S.

Sample Input

6 23

Sample Output

6


Hint: you can divied 6 as 1+2+3 and the LCM(1,2,3)=6 is the largest so we output 6%23=6.

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .