Taoxiang Number

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

Taoxiang is an ACMer in NJUST. He wants his name remembered in ACM team forever. One boring day, when he was writing some prime numbers on the blackboard, suddenly an amazing mind came up to his head. Given an integer N (2< N <=45), there are always several prime numbers which are not larger than N. So is there an integer S which can always obey the formula: S mod P= [sqrt (P)]? (P is all the prime numbers less than N; [Q] means the largest integer which is not larger than Q). If S exists, than Taoxiang will name this number: Taoxiang number! For example, if N=5, than the prime numbers not larger than 5 are 2, 3, 5. And the Taoxiang number of 5 will be 7.because 7%2=1, 7%3=1, 7%5=2. Taoxiang is so excited about this discovery, but he is puzzling how to find this number. Since you are kind enough, now, it’s your time to help him.

Input

The input will consist of several cases. In each case, just input one integer N, which means the given number. Pay attention! The integer N will bigger than 2 and not lager than 45

Output

In each case, just output the Taoxiang number in a single line. If there are several numbers which can obey the formula, only the smallest one will be Taoxiang number. If Taoxiang number doesn’t exist, just output “Impossible!”

Sample Input

5

Sample Output

7

Hint

Source

Cary & TaoXiang

提交代码