Given the value of an n you will have to find the modulo 100000000 value of the following expression: √√√√√ ⌊ 1⌋+⌊ 3⌋+⌊ 5⌋+...+⌊ 2i−1⌋+...+⌊ m⌋, 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, √√√ √ S=(⌊ 1⌋+⌊ 3⌋+⌊ 5⌋+...+⌊ m⌋)mod100000000 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 be processed. Output For each line of input produce one line of output. This line contains the value of S. Sample Input 9 19 29 10000000 0 Sample Output 9 26 49 38426378