Math Is Fun

Time limit1sMemory limit1024 MB

Summary

Given n up to 1e9, find the smallest positive integer x such that x times Euler's totient of x equals n, or report that none exists.

Level: Medium7 of 10
Topics: Number theory, Math, Binary search, Brute force
Solved: No attempts yet

Problem

Euler loves math so much that he is a math nerd who studies math all day long.

One day, while reading a math book to study, Euler came across a passage explaining the Euler phi function. The Euler phi function was described as follows.

The Euler phi function is written $\varphi(n)$ and denotes the number of positive integers from 1 to $n$ that are coprime with $n$ .

For example, $\varphi(6)$ denotes the number of integers from 1 to 6 that are coprime with 6; since these are 1 and 5, two numbers in total, $\varphi(6) = 2$ .

While reading the book carefully, Euler came up with a question. The question is as follows.

Given a positive integer $n$ , does there exist a positive integer $x$ satisfying $x\varphi(x) = n$ ?

Seeing Euler lost in thought, you decided to solve the problem yourself to resolve his curiosity. Therefore, you need to write a program that finds $x$ satisfying $x\varphi(x) = n$ .

Input

The first line gives $n$ . ( $1 \le n \le 10^9$ )

Output

If a positive integer $x$ satisfying $x\varphi(x) = n$ exists, print the smallest such $x$ ; otherwise, print $-1$ .

Examples3

Example 1
Input
```
2
```
Expected output
```
2
```
Example 2
Input
```
3
```
Expected output
```
-1
```
Example 3
Input
```
20
```
Expected output
```
5
```