Diagonal

Input

Contains no more than $1001$ lines. Each line contains a positive integer $N$ (N \le 10^{15}) — the minimum number of diagonals. The last line contains $0$ and should not be processed.

Output

For each test case, print its number and the smallest possible value of $n$ — the number of sides of the polygon.

Examples