Watson gives an integer $N$ to Sherlock and asks him: What is the number of divisors of $N$ that are divisible by 2?.

Input Format

First line contains $\mathbf{T}$, the number of testcases. This is followed by $\mathbf{T}$ lines each containing an integer $N$.

Output Format

For each testcase, print the required answer in one line.

Constraints

$1\leq T\leq100$

$1\leq N\leq10^9$

Sample Input

2
9
8

Sample Output

0
3

Explanation

9 has three divisors 1, 3 and 9 none of which is divisible by 2.

8 has four divisors 1,2,4 and 8, out of which three are divisible by 2.

见题面

见题面