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.
输入解释
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 the largest LCM modulo M of given S.
输入样例
6 23
输出样例
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.