Maximum Product Partition

Given a positive integer \(n\), partition it into a sum of at least two positive integers such that the product of these integers is maximized. For example, when \(n = 10\), one optimal partition is \(3 + 3 + 4\) and the product is \(3 \times 3 \times 4 = 36\). Similarly, when \(n = 8\), the maximum product is 18. Note that for small values like \(n=2\) and \(n=3\), the answers are 1 and 2 respectively.

The task is to compute the maximum product for any given \(n\) using efficient algorithms.

Constraints: \(n \ge 2\).

inputFormat

The input consists of a single line with one integer \(n\).

Input format:

n

outputFormat

Output the maximum product achievable by partitioning \(n\) into at least two positive integers. The output should be a single integer.

Output format:

answer

## sample

10

36