Divisors Divisible by 2

from __future__ import annotations
import os


def divisors(n: int) -> int:
    """
    n の約数のうち 2 で割り切れるものの個数を返す。

    【全単射による帰着】
        A = { d : d|n, 2|d }  ←→  B = { k : k | (n//2) }
        写像 φ: d → d/2  は A→B の全単射。
        よって |A| = |B| = #divisors(n // 2)

    Time Complexity:  O(√n)
    Space Complexity: O(1)
    """
    if n % 2 != 0:          # ① 奇数なら偶数約数はゼロ
        return 0

    m: int = n // 2         # ② 全単射により n//2 の約数カウントに帰着
    count: int = 0

    i: int = 1
    while i * i <= m:       # ③ i=1 から √m まで走査
        if m % i == 0:
            count += 1 if i * i == m else 2  # 完全平方→+1, それ以外→+2
        i += 1

    return count


if __name__ == "__main__":
    fptr = open(os.environ["OUTPUT_PATH"], "w")
    t: int = int(input().strip())
    for _ in range(t):
        fptr.write(str(divisors(int(input().strip()))) + "\n")
    fptr.close()