Though time passes, there is always someone we will never forget.
"The probability of being hit by a meteor is one in a billion, but it is much more miraculous, to meet you in my life." said Tom to Jerry with affection.
"One in a billion? I may not agree with you." answered Jerry proudly, "Let's do the math."
...
Thinking of the days they have happily spent together, Tom can't help bursting into tears. Though Jerry has been gone for a long time, Tom still misses him every day. He remembers it was a sunny afternoon when Jerry and him were lying in the yard, working on the probability of a man being hit by a meteor.
Unlike Jerry, he was always slow. Jerry got the answer soon, but Tom was stuck as usual. In the end, Tom lost patience and asked Jerry to tell him the answer.
"I can't be so straightforward," snickered Jerry, "the only thing I will tell you is that the answer is pqpq , where p,q≤n,gcd(p,q)=1p,q≤n,gcd(p,q)=1 ."
"Is it 1n1n ?"
"Is it 1n−11n−1 ?"
...
If answered "No" , he would try the minimum larger number that satisfies the requirement.
Tom only remembered nn given by Jerry, and kk, the times that he tried, but forgot what matters the most: Jerry's answer. Now, he wants you to help him find it.