Optimal Part Allocation in Containers

Given an integer \( n \), there are \( n \) containers numbered from \( 1 \) to \( n \). For each \( x \) (\( 1 \le x \le n \)), consider the scenario where container \( x \) is treated as the most important container. In this case, the capacity of container \( x \) is defined as \( x \), while the capacity of any other container \( i \) (where \( i \neq x \)) is defined as \( \gcd(i,x) \) (the greatest common divisor of \( i \) and \( x \)).

The task is to compute, for each \( x \) from \( 1 \) to \( n \), the maximum number of parts that the robots can place into all containers. In other words, for each \( x \), you should output the value:

[ \text{Answer}(x) = x + \sum_{\substack{i=1 \ i\neq x}}^{n} \gcd(i,x). ]

The output should consist of \( n \) lines, where the \( x \)-th line contains the answer for container \( x \) as the most important container.

inputFormat

The input consists of a single integer \( n \) (\( 1 \leq n \leq 1000 \)).

outputFormat

Output \( n \) lines. The \( x \)-th line should contain a single integer representing the maximum number of parts that can be placed into the containers when container \( x \) is considered the most important.

sample

2

2
3