Tìm số nguyên dương \(n\) nhỏ nhất thỏa mãn: \(\varphi(n) = k\) biết trước, với \(\varphi\) là hàm Euler. Nếu không tồn tại, in ra \(-1\).

Định dạng đầu vào

• Một dòng chứa số nguyên \(k\) (\(1 \le k \le 10^7\)).

Định dạng đầu ra

• Một số nguyên là \(n\) nhỏ nhất thỏa \(\varphi(n) = k\), hoặc \(-1\).

Ví dụ

Input:

4

Output:

5

Giải thích: \(\varphi(5)=4, \varphi(8)=4\), số nhỏ nhất là 5.

Ràng buộc

• 100% số điểm: \(k \le 10^7\).