Tom gives a number N to Roy and ask him to tell the total number of even divisors of the number N. Help Roy to answer the question of Tom.

INPUT:

First line contains the number of testcases T, followed by T lines each containing an integer N.

OUTPUT:

For each testcase, print the required answer in a singlr line.

Constraints:

1 ≤ T ≤ 100

1 ≤ N ≤ 1000000000

SAMPLE INPUT
2
9
8

SAMPLE OUTPUT
0
3

见题面

见题面