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 \(T\), the number of testcases. This is followed by \(T\) lines each containing an integer \(N\).

## Output Format

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

## Constraints

- \(1\leq T\leq 100\)
- \(1\leq N\leq 10^9\)

## Solution

When writing a number \(N\) as the product of its prime factors, we have \(N = p_1^{e_1}\cdot p_2^{e_2}\cdot p_3^{e_3}\dots\). From which the number of divisors follows as \(d(N) = (e_1+1)(e_2+1)(e_3+1)\dots\)

From the general case we have to count only the numbers that are divisible by 2. We have two cases for \(p_k=2\):

1) if \(e_k=0\) then the result must be zero, as no factor of 2 is present

2) if \(e_k\neq 0\) then we know that at least one factor of 2 is present. Since we want to know the number of divisors of \(N\) that are divisible by 2, we factor out 2 to say \(N=2M\). Calculating the number of divisors \(d(M)\) is then just \(d(M)=e_k (e_1+1)(e_2+1)\dots\)

Since \(p_i\equiv1\pmod{2}\) for all \(p_i\neq 2\), we can use this to avoid branching completely like so, using Rubys prime factorization library:

```
def divisors(n)
Prime.prime_division(n).inject(1) {|s, k|
s * (k[1] + k[0] % 2) * (1 - k[0] % 2)
}
end
```