Problem J
Jazz it Up!
Along with some friends you formed the Band of Atonal Percussionists and Cellists. You have been playing for some years together, but you feel unsatisfied with the current level of play. Doing research into some interesting new styles, you are gripped by the intricate details of the world of jazz.
While of course you cannot apply all the new things you have learned immediately, you want to start with improvising some nice new rhythmic figures in the music your band plays. You will play a rhythm where every bar has $n$ beats in it, but then you split up every beat into $m$ notes. In total, you will have $nm$ notes per bar.
Everyone in the band knows that there is no room for squares in jazz. So the number of notes in a bar should be squarefree. That is, there is no number $k > 1$ such that $k^2$ divides the number of notes in a bar.
The percussionist has already suggested a number of beats per bar $n$; now it is up to you to find a number of notes per beat that does not leave any room for squares.
In the second sample we have $n=30$ and $m=7$. This works because $2\leq m < n$ and $m\cdot n = 210$ has no divisor $k^2$ for any $k>1$.
Input
-
The input is a single squarefree integer $3\leq n\leq 10^5$.
Output
-
Output an integer $2 \leq m < n$ such that $m \cdot n$ is still squarefree.
If there are multiple possible solutions, you may output any one of them.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
30 |
7 |
| Sample Input 3 | Sample Output 3 |
|---|---|
13 |
10 |
