TIP3  Totient in permutation (hard)
In number theory, Euler's totient (or PHI function), is an arithmetic function that counts the number of positive integers less than or equal to a positive integer N that are relatively prime to this number N.
That is, if N is a positive integer, then PHI(N) is the number of integers K for which GCD(N, K) = 1 and 1 ≤ K ≤ N. We denote GCD the Greatest Common Divisor. For example, we have PHI(9)=6.
Interestingly, PHI(87109)=79180, and it can be seen that 87109 is a permutation of 79180.
Input
There is only one number M.
Output
For the given M, you have to print on a single line the value of N, for which 1 < N < M, PHI(N) is a permutation of N and the ratio N/PHI(N) produces a minimum. If there's several answers output the greatest, or if need, "No solution." without quotes.
Leading zeros are not allowed for integers greater than 0.
Example
Input: 22 Output: 21 Input: 222 Output: 63 Input: 2222 Output: 291
Explanations :
For the first case, in the range ]1..22[, the lonely number n for witch phi(n) is in permutations(n) is 21, (we have phi(21)=12). So the answer is obviously 21.
For the second case, in the range ]1..222[, there's two numbers n for witch phi(n) is in permutations(n), we have phi(21)=12 and phi(63)=36. But as 63/36 is equal to 21/12, we're taking the greater : 63.
For the third case, in the range ]1..2222[, there's four numbers n for witch phi(n) is in permutations(n), phi(21)=12, phi(63)=36, phi(291)=192 and phi(502)=250. Within those solutions 291/192 is the minimum, we output 291.
Constraints
1 < M < 10^27
If you got TLE, you should consider before TIP2. Enjoy.
Warning : don't try to investigate the input number, judge is strict and interactive ; test case is randomly changing, staying equivalent in difficulty. Please don't use spurious spaces and end your answer with '\n' ; e.g. "21\n" awaited for the sample.
There is many ways to optimize the solution for this problem, to get AC here, you'll need to find many of them.
Time limit allows python3 solutions.
There is different judges, time is the sum of them.
(Edit 20170211, after compiler changes : my Py3 solution ends in 25s, approx 2.5s per file, 10 files.)
hide comments
Min_25:
20160611 18:11:04
Note:


[Lakshman]:
20150730 15:45:13
I think the the problem has been fixed!!


Francky:
20140621 11:16:49
@Viplov : I will write to admin (third time) for this issue. I'm sorry for inconvenience. I'll tell you soon if your code can get AC, WA or TLE, ...


Viplov Jain:
20140621 07:03:51
@Francky my code is giving internal error.what does that mean?


Francky:
20140309 21:28:38
It seems 'interactive problems' have a bug, it's no longer possible to submit here, it causes 'internal error'. I will change my judge. Thanks to Mitch and Robert who confirmed the bug. I would like to use this kind of judge for my new problems, I'll use instead several IO files. Here too in the future. It will need a rejudge, in time...


Michael Kharitonov:
20130314 22:21:06
Why half of my submissions are disqualified? I know some of them are wrong, I kinda hope judge will turn them down, not you;)


Michael Kharitonov:
20130314 21:52:51
Test cases are not equivalent at least for my solution. I suggest at least 10 random cases, the results will be more reliable, plus (hard optimum + C), C  small const.

Added by:  Francky 
Date:  20130106 
Time limit:  20s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  TIP2 