Sum of Consecutive Natural Numbers

Time limit1sMemory limit128 MB

Summary
For numbers up to 2^31, count the ways each can be expressed as a sum of two or more consecutive positive integers.
Level

Medium4 of 10

Topics
Math, Number theory
Solved
No attempts yet

Problem

Given a natural number N, count how many ways it can be written as the sum of at least two consecutive natural numbers.

Two representations are different if they start with a different natural number or use a different number of terms. Every term must be a positive integer, and adjacent terms must differ by 1.

Input

The first line contains the number of test cases T.

Each of the next T lines contains one natural number N. Every N is less than 2^31.

Output

For each test case, print one line containing the number of ways to write N as the sum of at least two consecutive natural numbers.

Examples1

  1. Example 1

    Input
    7
6
9
8
1800
987654321
987654323
987654325
    Expected output
    1
2
0
8
17
1
23