Problem A
Odd Root Sum
Input: Standard Input

Output: Standard Output

 
Given the value of an n you will have to find the modulo 100000000 value of the following expression:
 
, where m is the largest odd number not greater than n

 

Or in other words you will have to find the value of S where,

 

.

 

Input

The input file contains at most 30000 lines of inputs. Each line contains a single 64-nit signed integer which denotes the value of n. Input is terminated by a line containing a single zero which should not b processed.

 

Output

For each line of input produce one line of output. This line contains the value of S.

 

Sample Input                               Output for Sample Input

9

19

29

10000000

0

9

26

49

38426378

Problemsetter: Shahriar Manzoor

Special Thanks To: Derek Kisman