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
from math import floor,sqrt

n=int(input())
for i in range(n):
  m=int(input())
  if m%4==1 or m%4==2:
   print(0)
  else:
   s=m*(m+1)//2
   res=0
   sm=s//2
   p1=floor((sqrt(4*s+1)-1)/2)
   s1=p1*(p1+1)//2
   p=[p1-1,p1,p1+1]
   s=[s1-p1,s1,s1+p[2]]
   l=[sm-s[0],sm-s1,sm-s[2]]
   for j in range(len(l)):
    if l[j]==0:
     res+=(p[j]*(p[j]-1)+(m-p[j]-1)*(m-p[j]))//2
    elif l[j]>0 and l[j]<m:
     res+=min([l[j],m-l[j],p[j],m-p[j]])
     
   print(res)
   

from math import floor,sqrt

n=int(input())
for i in range(n):
  m=int(input())
  if m%4==1 or m%4==2:
   print(0)
  else:
   s=m*(m+1)//2
   res=0
   sm=s//2
   p1=floor((sqrt(4*s+1)-1)/2)
   s1=p1*(p1+1)//2
   p=[p1-1,p1,p1+1]
   s=[s1-p1,s1,s1+p[2]]
   l=[sm-s[0],sm-s1,sm-s[2]]
   for j in range(len(l)):
    if l[j]==0:
     res+=(p[j]*(p[j]-1)+(m-p[j]-1)*(m-p[j]))//2
    elif l[j]>0 and l[j]<m:
     res+=min([l[j],m-l[j],p[j],m-p[j]])
     
   print(res)
   
