Minimum Password Attempts to Activate the Shrine

Madeline faces a mysterious shrine guarded by a secret password. She recalls that the password has length 3 and that each digit has n possible symbols; that is, the secret password belongs to the set \(\{0,1,\dots,n-1\}^3\) (so there are \(n^3\) possibilities). Through her observation, she discovered that if an attempted password matches the unknown standard password in at least 2 out of the 3 positions (i.e. the Hamming distance is at most 1), the shrine will light up and grant her the crystal heart.

Your task is to help Madeline by computing the minimum number of password attempts she must try so that, no matter what the secret password is, at least one of her attempts will have at least two digits in the exact positions matching the secret password.

More formally, let a password be a triple \(p=(p_1,p_2,p_3)\) where \(p_i\in\{0,1,\dots,n-1\}\). An attempted password \(a=(a_1,a_2,a_3)\) covers \(p\) if it has at least 2 coordinates such that \(a_i=p_i\). Equivalently, if the Hamming distance \(d(a,p)\) (i.e. the number of positions in which they differ) is at most 1 then \(a\) is successful for \(p\). Determine the minimum size of a set of attempts \(S\subseteq\{0,1,\dots,n-1\}^3\) such that for every \(p\in\{0,1,\dots,n-1\}^3\), there exists an attempt \(a\in S\) with \(d(a,p)\le1\>.

Note: In this problem the input is a single integer \(n\) (with \(n\ge1\)). For the special cases that have been studied, it turns out that the answer can be given by the following observations:

• If \(n=1\) then there is only one possible password, so the answer is 1.
• If \(n=2\), one optimal strategy is to try 000 and 111; thus the answer is 2.
• It is known that for \(n=3\) an optimal covering set has size 5.
• For \(n\ge4\), one may prove that an optimal answer is given by:
  • If \(n\) is even, the answer is \(\frac{n^2}{2}\).
  • If \(n\) is odd (and \(n\ge5\)), the answer is \(\lfloor\frac{n^2}{2}\rfloor\).

You may assume that the input value of \(n\) is such that the answer (which is the minimum number of attempts) can be computed using the above formulas with a special-case adjustment for \(n=1\) and \(n=3\>.

It is guaranteed that the set of test cases used to judge your solution are covered by the formulas above.

inputFormat

The input consists of a single integer \(n\) (\(n \ge 1\)), representing the number of possibilities for each digit in the 3-digit password.

outputFormat

Output a single integer, which is the minimum number of password attempts required to guarantee that at least one attempt matches the secret password in at least 2 positions.

sample

1

1