Longest Anti-chain of Divisors

In order theory, an anti‐chain is a set of elements none of which divides another. Given a positive integer \( n \), let \( S(n) \) be the set of all divisors of \( n \). A subset \( A \) of \( S(n) \) is called an anti‐chain if either \( A \) contains only one element or for any two distinct elements \( a, b \in A \), neither \( a \mid b \) nor \( b \mid a \) holds.

For example, consider \( n=30 \). We have \( S(30)=\{1,2,3,5,6,10,15,30\} \). Note that:

• The set \( \{2,5,6\} \) is not an anti‐chain because \( 2 \mid 6 \).
• The set \( \{2,3,5\} \) is an anti‐chain.

Let \( f(n) \) be the length of the longest anti‐chain in \( S(n) \). Your task is to compute:

[ ans = \sum_{k=1}^{n} f(k). ]

If you cannot solve it, beware that hhoppitree might pounce on you!

inputFormat

The input contains a single integer \( n \) (\( n \ge 1 \)).

outputFormat

Output a single integer representing \( ans = \sum_{k=1}^{n} f(k) \), where \( f(k) \) is the maximum size of an anti‐chain in \( S(k) \).

sample

1

1