Minimum Number Satisfying Euler's Totient Equation

Given a positive integer n, find the smallest positive integer x such that the Euler's totient function \(\varphi(x) = n\). If no such positive integer exists, output -1.

The Euler's totient function \(\varphi(x)\) is defined as the number of integers in \([1, x]\) that are coprime with x.

inputFormat

The input consists of a single line that contains a positive integer n.

outputFormat

Output the smallest positive integer x for which \(\varphi(x) = n\). If no such x exists, output -1.

sample

1

1