The number of diagonals of an n-gon is not less than N. What is the minimum possible value of n?

Input

Contains less than 1001 lines. Each line contains a positive integer N (N ≤ 1015) that indicates the minimum possible number of diagonals. Input is terminated by a line with one 0 that should not be processed.

Output

For each test case produce one line that contains serial number and the minimum possible value for n (number of sides).