Gold Coins

Interview

Time limit1sMemory limit128 MB

Summary

For each number of days, add up the gold coins when the knight is paid N coins on each of N consecutive days.

Level: Easy3 of 10
Topics: Math, Implementation, Simulation, Prefix sum
Solved: No attempts yet

Problem

The king pays his loyal knight in gold coins. On the first day of service the knight receives $1$ gold coin. On each of the next $2$ days (the 2nd and 3rd days of service) the knight receives $2$ gold coins. On each of the next $3$ days (the 4th, 5th, and 6th days) the knight receives $3$ gold coins. On each of the next $4$ days (the 7th through 10th days) the knight receives $4$ gold coins.

This pattern of payments continues forever: after being paid $N$ gold coins on each of $N$ consecutive days, the knight is paid $N+1$ gold coins on each of the next $N+1$ consecutive days, for every positive integer $N$ .

Given a number of days, determine the total number of gold coins the knight has been paid over that many days, counting from Day 1.

Input

The input contains at least one and at most $1001$ lines. Each line except the last holds one test case: a single integer in the range $1 \le d \le 10000$ giving a number of days. A line containing the number $0$ marks the end of the input and is not a test case.

Output

For each test case print one line containing the number of days from that test case, a single space, and the total number of gold coins paid to the knight over those days, counting from Day 1.

Examples2

Example 1

Input

Expected output

10 30
6 14
7 18
11 35
15 55
16 61
100 945
10000 942820
1000 29820
21 91
22 98

Example 2
Input
```
2
0
```
Expected output
```
2 3
```