Jazz it Up!

Time limit1sMemory limit512 MB

Summary

Given a squarefree n between 3 and 100000, find m with 2 <= m < n such that m*n is also squarefree.

Level: Easy3 of 10
Topics: Math, Number theory, Brute force, Implementation
Solved: No attempts yet

Problem

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 ≤ m < n and m × n = 210 has no divisor k^2 for any k > 1.

Input

The input is a single squarefree integer 3 ≤ n ≤ 105.

Output

Output an integer 2 ≤ m < n such that m × n is still squarefree.

If there are multiple possible solutions, you may output any one of them.

Examples3

Example 1
Input
```
3
```
Expected output
```
2
```
Example 2
Input
```
30
```
Expected output
```
7
```
Example 3
Input
```
13
```
Expected output
```
10
```