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