William thinks 89 is an unlucky number for him. But he still wants to know more about 89. He knows 89 is the 24th prime number, and also a Fibonacci number after searching on the internet.
Recently, William starts to study some problems about right triangles. He call a right triangle is unlucky if lengths of its both legs are integers and the length of the hypotenuse is a multiple of √89. For example, a right triangle with three edges (5,8,√89) is unlucky, (4,47,5√89), (17,44,5√89), and (10,16,2√89) are also unlucky. He thinks each unlucky triangle has an energy which is defined by its hypotenuse. The energy of an unlucky triangle is its hypotenuse divided by √89. For example, the energy of (5,8,√89) is 1, and the energy of (71,100,13√89) is 13. William is very curious about the average circumference of all the unlucky triangles whose energy is less than or equal to n. The circumference of a triangle is the sum of its three sides. Can you help him? William is expecting a precise answer.
Input
There are multiple cases. Each case is an integer number n in a line. (1≤ n≤ 108, the sum of n in the whole input is less than 2*108)
Output
Each output for one case has 5 lines. Each output should be in the following format:
Print a blank line after each case. Please refer to the sample output.
Sample Input
1
8
9
89
99999999
Sample Output