Send a Table#1563

Send a Table

1 second

128 megabytes

Very easy

Jimmy needs to compute a function $f (x, y)$ f(x, y), where $x$ and $y$ are integers from $1$ to $n$ . If he knows $f (x, y)$ f(x, y), he can easily derive $f (k \cdot x, k \cdot y)$ f(k \cdot x, k \cdot y) for any integer $k$ by applying simple calculations to $f (x, y)$ f(x, y) and $k$ .

Note that the function $f$ is not symmetric, so $f (x, y)$ f(x, y) cannot be derived from $f (y, x)$ f(y, x).

For example, if $n = 4$ n = 4, Jimmy initially needs to know $11$ out of the $16$ possible input pairs:

The remaining $5$ values can be derived from the already known ones:

$f (2, 2)$ f(2, 2), $f (3, 3)$ f(3, 3), and $f (4, 4)$ f(4, 4) from $f (1, 1)$ f(1, 1);
$f (2, 4)$ f(2, 4) from $f (1, 2)$ f(1, 2);
$f (4, 2)$ f(4, 2) from $f (2, 1)$ f(2, 1);

Input

The input consists of at most $600$ lines. Each line contains one integer $n$ ( $1 \leq n \leq 50000$ 1 \le n \le 50000). The last line contains $0$ and should not be processed.

Output

For each input value of $n$ , output on a separate line the minimum number of function values Jimmy needs to know to compute all $n^{2}$ n^2 values $f (x, y)$ f(x, y).

Examples

Example 1

Loading

f (x, y)

f (x, y)

f (k \cdot x, k \cdot y)

f (x, y)

f (x, y)

f (y, x)

n = 4

f (2, 2)

f (3, 3)

f (4, 4)

f (1, 1)

f (2, 4)

f (1, 2)

f (4, 2)

f (2, 1)

1 \leq n \leq 50000

n^{2}

f (x, y)