Optimal Contiguous Circle Sums

You are given a circle divided into n sectors (with n an integer satisfying \(1\le n\le8\)). In each sector you must place a positive integer \(a_i\). After placing the numbers, you are allowed to form new numbers by selecting one number from a single sector, or by choosing one number from each of a set of consecutive (adjacent) sectors along the circle. (Note that since the sectors are arranged in a circle, the segment may wrap around from the last sector to the first one.)

In other words, if the sectors (in order) are \(a_1,a_2,\dots,a_n\) and if we define a contiguous segment (possibly wrapping around) as a sequence \(a_i, a_{i+1}, \dots, a_j\) (indices taken modulo \(n\) so that a segment may start near \(a_n\) and continue with \(a_1\), etc.), then each contiguous segment has a sum. Your task is to choose the numbers \(a_1,a_2,\dots,a_n\) so that the set of these sums exactly covers a continuous integer sequence \[ \{1,2,3,\dots,i\} \] with \(i\) as large as possible.

For example, when n = 3, one optimal assignment is \(a_1=1, a_2=2, a_3=4\). The sums of the contiguous segments are:

• Single sectors: 1, 2, 4.
• Two adjacent sectors: \(1+2=3\), \(2+4=6\), and \(4+1=5\) (wrap‐around).
• All three sectors: \(1+2+4=7\).

The set of sums is \(\{1,2,3,4,5,6,7\}\), which is exactly \(\{1,2,\dots,7\}\). Hence, the maximum possible \(i\) is 7 for \(n=3\).

Your task is: Given n, output the maximum achievable \(i\) when the numbers in the sectors are chosen optimally.

Note: Since n is very small (\(1\le n\le8\)), it is known by analysis that the maximum values of \(i\) are as follows:

• n = 1: i = 1
• n = 2: i = 3
• n = 3: i = 7
• n = 4: i = 12
• n = 5: i = 18
• n = 6: i = 26
• n = 7: i = 35
• n = 8: i = 45

inputFormat

The input consists of a single line containing one integer n (\(1\le n\le8\)).

outputFormat

Output a single integer, the maximum possible \(i\) such that there exists an assignment of positive integers to the sectors for which all sums of contiguous sectors (including those that wrap around) exactly cover \(\{1,2,\dots,i\}\).

sample

1

1