There are N straight lines in a 3D coordinate. Your job is to find the maximum number of intersections for N straight lines.
The input contains multiple cases. In each test case, there is an integer N which indicates the number of straight lines. ( 0 < N < 1000000 ) When N is equal to 0, it is the end of the input file.
Print the result mod 10000 in a newline.