Maximizing the Product of Two Primes

Given an integer S, which is the sum of two prime numbers, determine the maximum possible product of these two primes.

The problem can be formulated as follows: find two prime numbers \(p\) and \(q\) such that \(p+q=S\), and maximize \(p\cdot q\). Note that for a fixed sum, the product is maximized when the two numbers are as close as possible. In particular:

• If \(S\) is even and \(\frac{S}{2}\) is a prime, then the answer is \(\left(\frac{S}{2}\right)^2\).
• If \(S\) is odd, then one of the primes must be 2 and the other \(S-2\) (provided \(S-2\) is prime). Otherwise, when \(S\) is even but \(\frac{S}{2}\) is not prime, one must search for a pair \(p\) and \(S-p\) (with \(p \leq S-p\)) that are both prime, and choose the pair yielding the maximum product.

You may assume that the input S satisfies the condition of being expressible as the sum of two primes.

inputFormat

The input consists of a single integer S (S \(\ge 5\)).

outputFormat

Output a single integer representing the maximum possible product of two prime numbers whose sum is S.

sample

8

15