Nam rất yêu thích các con số lớn, vì vậy với số nguyên dương N bất kỳ, bạn ấy muốn biểu diễn N thành tổng các số hạng sao cho tích M của các số hạng đó là lớn nhất. Hãy lập trình để giúp Nam tìm ra số nguyên lớn đó.

Dữ liệu vào:

Tệp văn bản CAU4.INP gồm 1 dòng chứa số nguyên dương N (N ≤ 10000).

Kết quả:

Ghi vào tệp văn bản CAU4.OUT gồm 1 dòng chứa số M tìm được.

Ví dụ:

CAU4.INP
5

CAU4.OUT
6

Giải thích: 5 = 2 + 3; 2 × 3 = 6

CAU4.INP
9

CAU4.OUT
27

Giải thích: 9 = 3 + 3 + 3; 3 × 3 × 3 = 27

CAU4.INP
13

CAU4.OUT
108

Giải thích: 13 = 3 + 3 + 3 + 4; 3 × 3 × 3 × 4 = 108

Gợi ý thuật toán (tham khảo):

Để tích lớn nhất, nên tách N thành nhiều số 3 nhất có thể, phần dư xử lý như sau: nếu dư 1 thì đổi 3 + 1 thành 2 + 2; nếu dư 2 thì thêm 2, nếu dư 0 thì chỉ toàn số 3.

Ràng buộc (phân điểm):

- 40% test: N ≤ 50.
- 30% test: N ≤ 100.
- 30% test: N ≤ 10000.