Given the value of an n you will have to find the modulo 100000000 value of the following expression:
floor(sqrt(1)) + floor(sqrt(3)) + floor(sqrt(5)) + ... + floor(sqrt(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 = floor(sqrt(1)) + floor(sqrt(3)) + floor(sqrt(5)) + ... + floor(sqrt(m)) MOD 100000000
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.
For each line of input produce one line of output. This line contains the value of S.