Unlucky Right Triangle

Time Limit: 5 Seconds

Memory Limit: 65536 KB

Description

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:

***************************************************
*          Numerator1             Numerator2    __*
*Integer1------------ + Integer2------------ x V89*
*        Denominator1           Denominator2      *
***************************************************
Each mixed fraction should be irreducible. When numerator is 0, the proper fraction part should be omitted. If Numerator2 is 0 and Integer2 is 1, then "1 x " part should be omitted too. The numerator and the denominator need to be right-aligned. The "---" part should be as same long as the corresponding denominator.

Note the characters other than digits used in the output: '*'(Asterisk, ascii code 42), ' '(Space, ascii code 32), '_'(Underscore, ascii code 95), '-'(Hyphen or minus sign, ascii code 45), 'x'(letter x, ascii code 120), and 'V'(letter V, ascii code 86).

Print a blank line after each case. Please refer to the sample output.

Sample Input

1
8
9
89
99999999

Sample Output

**********
*      __*
*13 + V89*
*        *
**********

***************
*      3    __*
*58 + 4- x V89*
*      5      *
***************

****************
*   4        __*
*63-- + 5 x V89*
*  11          *
****************

********************
*   37     13    __*
*598-- + 48-- x V89*
*   90     18      *
********************

**********************************************
*          93224754            97600661    __*
*620114538--------- + 51235071--------- x V89*
*         106191655           318574965      *
**********************************************

Hint

If n is 108, there are 637149947 kinds of right triangles in different shapes and sizes.

Explanation for n=8, we can find 10 unlucky right triangles whose energy is no more than 8. They are (5,8,√89), (10,16,2√89), (15,24,3√89), (20,32,4√89), (4,47,5√89), (17,44,5√89), (25,40,5√89), (30,48,6√89), (35,56,7√89), and (40,64,8√89). The sum of circumferences is 580+46√89, so the average circumference is (580+46√89)/10.

Source

None

提交代码