Số chính phương hay còn gọi là sô hình vuông là số tự nhiên có căn bậc hai của nó là một số tự nhiên. Số ước dương của số chính phương là một số lẻ.

Số nguyên tố có đúng chính xác hai ước số.

Vậy số có chính xác có 3 ước số là số như thế nào, ví dụ số 25 có 3 ước số là 1, 5, 25.

Bài toán hôm nay là tìm các số có 3 ước số, cụ thể là: Cho một số tự nhiên ~n~, hãy tìm số tự nhiên ~m~ nhỏ nhất thỏa ~m \ge n~ và ~m~ có đúng 3 ước số.

Input

Dòng duy nhất chứa số tự nhiên ~n~.

Output

In ra số cần tìm.

Constraint

• Subtask 1 (40%): ~n \le 10^3~.

• Subtask 2 (60%): ~n \le 10^6~.

• Subtask 3 (100%): ~n \le 10^{12}~.

Sample Input

20

Sample Output

25