Strange Recursive Function Sum

Consider a strange recursive function defined by zzq. For two positive integers a and b, the function f(a, b) is defined as follows:

[ f(a,b)= \begin{cases} 0, & \text{if } a=b,\[6pt] f(a-b, 2b)+1, & \text{if } a>b,\[6pt] f(2a, b-a)+1, & \text{if } a<b. \end{cases} ]

However, it is observed that for many inputs the recursion never terminates. In such cases, we define f(a, b) = 0 if the recursion becomes infinite.

An important observation is that in every recursive call the sum \(S = a+b\) remains invariant. Hence if \(S\) is not a power of two then the process never reaches the termination condition \(a=b\) (which would imply \(a=b=S/2\)). Therefore we can conclude that:

• If \(a+b\) is not a power of 2 then \(f(a, b)=0\).
• If \(a+b=2^k\) for some positive integer \(k\), then f(a,b) is defined as the number of steps needed to reach \(a=b=2^{k-1}\) using the above recursion.

Your task is: Given an integer \(n\), compute

[ \sum_{i=1}^n \sum_{j=1}^n f(i,j). ]

Note: Although the given recursive function is reminiscent of the Euclidean algorithm, its transformation is different. You may use the observation that \(a+b\) is invariant and that termination (\(f(i,j)\neq 0\)) occurs if and only if \(i+j\) is a power of two. If \(i+j\) is a power of two, let \(S=i+j\) and note that if we write \(i = \frac{S}{2}-d\) (so that \(d=|i-\frac{S}{2}|\)), then we can compute f(i,j) by repeatedly transforming \(d \to |\frac{S}{2}-2d|\) until \(d=0\). If the recursion never terminates, define f(i,j)=0.

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le 10^4\) or as specified), representing the range of integers. You need to compute the sum \(\sum_{i=1}^n \sum_{j=1}^n f(i,j)\).

outputFormat

Output a single integer which is the value of the sum.

sample

1

0