Họ hàng là những người có quan hệ huyết thống, ở Việt Nam thường có các mối quan hệ họ hàng thân thiết. Nhìn chung quan hệ họ hàng trong gia đình ở Việt Nam rất phức tạp, người Việt có thuật ngữ "dây mơ rễ má" để hình dung những mối quan hệ phức tạp của họ.

Một số nguyên dương được gọi làsố họ hàngkhi nó chỉ có các ước nguyên tố là 2, 3 hoặc 5. Số 100 là một số họ hàng vì nó có các ước nguyên tố là 225*5.

Ví dụ: dãy số gồm 10 số họ hàng đầu tiên là: 2, 3, 4, 5, 6, 8, 9, 10, 12, 15.

Yêu cầu: Viết chương trình xác định số họ hàng thứ ~n~. Biết số họ hàng thứ 2000 lớn hơn 10^9.

Input

Duy nhất một số nguyên dương ~n~ (~n \le 2000~)

Output

In ra số họ hàng thứ ~n~

Sample

Input #1

1

Output #1

2

Input #2

6

Output #2

8

Input #3

9

Output #3

12

Hint

Với các test mẫu:

*   Số họ hàng thứ nhất là ~2~

*   Số họ hàng thứ sáu là ~8~

*   Số họ hàng thứ chín là ~12~