We define consecutive sequence as a sequence of integer numbers {n, n+1, n+2 ... n+m}. For each given positive integer N ≤ 10⁷ calculate number of such sequences which sum is equal to N.

Input

The input file consists of multiple lines (about 10³ in the first data set and 10⁵ in the second), each line contains integer N. The input is terminated with N = 0, which should not be processed.

Output

Expected number in each line.

Example

Input:
500
0

Output:
8