Người ta sắp xếp các số hoàn hảo theo thứ tự tăng dần: 6, 28, 496, ...

Yêu cầu bạn tìm số hoàn hảo thứ K trong dãy số này.

Input:

• Một số nguyên dương K.

Giới hạn:

• 1 <= K <= 8.

(Vì trong giới hạn 64-bit chỉ có 8 số hoàn hảo).

Output:

• In ra số hoàn hảo thứ K.

Ví dụ

Input:

2

Output:

28

Gợi ý thuật toán:

Vì số lượng số hoàn hảo rất ít, bạn không thể "tìm kiếm" chúng. Hãy "sinh" ra chúng.

Duyệt các số nguyên tố p = 2, 3, 5, 7, 13, 17, 19, 31...

Tính M = 2^p - 1. Nếu M là số nguyên tố -> Tính N = 2^(p-1) * M và lưu vào danh sách kết quả.