You are given a positive integer $N$. Consider the sequence $S = (1, 2, \ldots, N)$. You should choose two elements of this sequence and swap them.
A swap is nice if there is an integer $M$ ($1 \le M < N$) such that the sum of the first $M$ elements of the resulting sequence is equal to the sum of its last $N-M$ elements. Find the number of nice swaps.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains a single integer $N$.

-----Output-----
For each test case, print a single line containing one integer ― the number of nice swaps.

-----Constraints-----
- $1 \le T \le 10^6$
- $1 \le N \le 10^9$

-----Subtasks-----
Subtask #1 (10 points):
- $T \le 10$
- $N \le 10^3$
Subtask #2 (30 points):
- $T \le 10$
- $N \le 10^6$
Subtask #3 (60 points): original constraints

-----Example Input-----
5
1
2
3
4
7

-----Example Output-----
0
0
2
2
3

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# cook your dish here\nimport math\nt= int(input())\nfor test in range(t):\n n = int(input())\n #If total sum is not even, then we cant divide array in 2 equal sum arrays\n sum_array = (n*(n+1))//2\n if sum_array%2 !=0:\n  print(0)\n  continue\n # 1 2 3 4 5 6 7 8 --  9 10 11 12  ---> divide closest to ideal sum\n ideal_sum = sum_array//2\n partition_sum = 0\n partition_ind = 0\n n_swap = 0\n for i in range(1,n+1):\n  if i + partition_sum > ideal_sum:\n   partition_ind = i-1\n   break\n  else:\n   partition_sum += i\n n_swap = n - partition_ind\n f = math.factorial\n if partition_sum == ideal_sum:\n  if partition_ind >= 2:\n   n_swap += (f(partition_ind) // 2 // f(partition_ind-2))\n  if n-partition_ind >= 2:\n   n_swap += (f(n-partition_ind) // 2 // f(n-partition_ind-2))\n   \n print(n_swap)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13235