Sum of GCD Squares Table

After passing a series of interviews and tests, Xiao Ming has successfully joined Macrohard. His first task is to fill an n × n table. The rows and columns are numbered from \(1\) to \(n\), and the element at position \(i, j\) is \((\gcd(i,j))^2\), where \(\gcd(i,j)\) denotes the greatest common divisor of \(i\) and \(j\).

For example, the top-left 4×4 portion of the table is:

1  1  1  1
1  4  1  4
1  1  9  1
1  4  1 16

Your task is to compute the sum of all the elements in this table.

The mathematical formulation of each table element is given by:

[ a_{i,j} = \left(\gcd(i, j)\right)^2, \quad 1 \le i, j \le n. ]\n

You need to output the value of:

[ S = \sum_{i=1}^{n} \sum_{j=1}^{n} \left(\gcd(i, j)\right)^2. ]

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le 10^5\) or as specified), which indicates the number of rows and columns of the table.

outputFormat

Output a single integer representing the sum of all the elements in the table.

Recall that the \( (i, j) \) element of the table is \((\gcd(i,j))^2\).

sample

1

1