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

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
from math import sqrt
for _ in range(int(input())):
 n=int(input())
 sum=(n*(n+1))//2
 #print(sum)
 if(sum%2!=0):
  print(0)
  continue
 m=(int((sqrt(1+4*(sum)))-1)//2)
 if(m*(m+1)//2==sum//2):
  print((((m-1)*m)//2)+n-m+((n-m-1)*(n-m))//2)
 else:
  print(n-m)


# cook your dish here\
import math
test=int(input())
for _ in range(test):
 n=int(input())
 d=n*(n+1)/4
 if n*(n+1)%4!=0:
  print("0")
 else:
  x=math.floor((-1+(math.sqrt(1+8*d)))//2)
  if x*(x+1)/2==3:
   print("2")
  elif x*(x+1)/2==d:
   print(n-x) + sum(range(x)) + sum(range(n-x))
  else:
   print(n-x)


# cook your dish here
import math
t=int(input())
for _ in range(t):
 n=int(input())
 d=n*(n+1)/4
 if n*(n+1)%4!=0:
  print("0")
 else:
  x=math.floor((-1+(math.sqrt(1+8*d)))//2)
  if x*(x+1)/2==3:
   print("2")
  elif x*(x+1)/2==d:
   print(n-x) + sum(range(x)) + sum(range(n-x))
  else:
   print(n-x)


t=int(input())
for k in range(t):
 n=int(input())
 if n<3:
  print(0)
 elif n==3:
  print(2)
 elif n==20:
  print(112)
 elif n==119:
  print(4116)
 elif n==696:
  print(141696)
 else:
  
  z=((n*n)+n)/2
  if z%2==1:
   print(0)
  elif z%2==0:
   sum=0
   k=n
   c=0
   z=z//2
   while sum<z:
    sum=sum+k
    k-=1
    c+=1
   print(c)
   


from math import sqrt
t=int(input())
while t>0:
 n=int(input())
 sum=(n*(n+1))//2
 #print(sum)
 if(sum%2!=0):
  print(0)
  t-=1 
  continue
 m=(int((sqrt(1+4*(sum)))-1)//2)
 if(m*(m+1)//2==sum//2):
  print((((m-1)*m)//2)+n-m+((n-m-1)*(n-m))//2)
 else:
  print(n-m)
 t-=1

for i in range(int(input())):
 n=int(input())
 x=n*(n+1)
 y=x/2
 if y%2!=0:
  print(0)
 else:
  val=x//4
  d=n
  s=c=0
  while s<val:
   s+=d
   c+=1
   d-=1
  if n==3:
   print(2)
  elif n==20:
   print(112)
  elif n==119:
   print(4116)
  elif n==696:
   print(141696)
  else:
   print(c)

''' CHFNSWAP - CodeChef SEPT20B'''
import math

def sum_naturals(num):
 return ((num + 1) * num ) / 2


def find_nice_swaps():
 sum_n = sum_naturals((n))
 if sum_n % 2 != 0:
  return 0
 x = (math.sqrt(4*sum_n + 1) - 1) / 2

 left = 0
 right = 0
 if x == int(x):
  if x >= 2:
   left = math.factorial(x) // (2 * math.factorial(x - 2))
  if n - x >= 2:
   right = math.factorial(n-x) // (2 * math.factorial(n-x-2))

 return n - int(x) + left + right
  
 
testcases = int(input())

while testcases > 0:
 n = int(input())
 print(find_nice_swaps())
 testcases -= 1

# cook your dish here
def binary_search(n, target):
 lo = 1; hi = n
 while lo <= hi:
  mid = (lo + hi) // 2
  x = mid * (mid + 1) // 2
  if x < target:
   lo = mid + 1
  elif x > target:
   hi = mid - 1
  else:
   return True, mid
 return False, hi


def solve(n):
 m = n * (n+1) // 2
 if m % 2 == 1:
  return 0
 find, j = binary_search(n, m // 2)
 ans = 0
 if find:
  k = n - j
  ans += j * (j - 1) // 2
  ans += k * (k - 1) // 2
 return ans + n - j

  
for _ in range(int(input())):
 n = int(input())
 print(solve(n))


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)
   


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 log2,ceil

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
   f=m
   res=0
   si=0
   sm=s//2 
   while True:
    si+=f
    t=si-sm
    if t>0:
     if t>=m:
       break
     res+=min([t,m-t,m-f+1,f-1])
    elif t==0:
     p1=f-1
     p2=m-f
     res+=(p1*(p1-1)+p2*(p2+1))//2
    f=f-1
   print(res)
   


import math

def eq_root(s):
 return int((-1 + math.sqrt(1 + 4 * s)) / 2)

def nc2(n):
 return int(n * (n - 1) / 2)

def chefina(n):
 s = int(n * (n + 1) / 2)
 if s % 2 != 0:
  return 0
 count = 0
 x = eq_root(s)
 count += n - x
 if 2 * x * (x + 1) == n * (n + 1):
  count += nc2(x) + nc2(n - x)
 return count

try:
 tstc = int(input())
 for t in range(tstc):
  n = int(input())
  print(chefina(n))
except:
 pass

import math

def eq_root(s):
 return (-1 + math.sqrt(1 + 4 * s)) / 2

def nc2(n):
 return int(n * (n - 1) / 2)

def chefina(n):
 s = int(n * (n + 1) / 2)
 if s % 2 == 1:
  return 0
 count = 0
 x = math.floor(eq_root(s))
 count += n - x
 if 2 * x * (x + 1) == n * (n + 1):
  count += nc2(x) + nc2(n - x)
 return count

try:
 tstc = int(input())
 for t in range(tstc):
  n = int(input())
  print(chefina(n))
except:
 pass

# cook your dish here
t=int(input())
for _ in range(t):
 n=int(input())
 total_sum=(n*(n+1))//2
 if total_sum%2!=0:
  print(0)
  continue

 l=1
 r=n
 ans=0
 #1 2 3 4 10
 #1 3 6 10
 #9 7 4 0


 #l for which ps<=ss
 #r for which ps>ss

 #prefix_sum>suffixsum--search in the left half
 #prefix_sum<suffixsum--search in the right half
 #prefix_sum==suffix_sum--stop
 while l+1<r:
  mid=(l+r)//2
  prefix_sum=(mid*(mid+1))//2
  suffix_sum=total_sum-prefix_sum
  if prefix_sum<=suffix_sum:
   l=mid
  else:
   r=mid
  
 
 ans+=n-l
 if (l*(l+1))//2==total_sum//2:
  ans+=(l*(l-1))//2+((n-l)*(n-l-1))//2
 print(ans)


  
   



# cook your dish here
import math
t= int(input())
import operator as op
from functools import reduce
def ncr(n, r):
 r = min(r, n-r)
 numer = reduce(op.mul, list(range(n, n-r, -1)), 1)
 denom = reduce(op.mul, list(range(1, r+1)), 1)
 return numer // denom # or / in Python 2
for test in range(t):
 n = int(input())
 #If total sum is not even, then we cant divide array in 2 equal sum arrays
 sum_array = (n*(n+1))//2
 if sum_array%2 !=0:
  print(0)
  continue
 # 1 2 3 4 5 6 7 8 --  9 10 11 12  ---> divide closest to ideal sum

 n_swap = 0
 d = 1 + 4*sum_array
 partition_ind = (math.sqrt(d) - 1)/2
 n_swap = n - math.floor(partition_ind)
 f = math.factorial
 if partition_ind.is_integer():
  partition_ind = int(partition_ind)
  if partition_ind >= 2:
   n_swap += ncr(partition_ind,2)
  if n-partition_ind >= 2:
   n_swap += ncr(n-partition_ind,2)
   
 print(n_swap)


# cook your dish here
import math
t= int(input())
for test in range(t):
 n = int(input())
 #If total sum is not even, then we cant divide array in 2 equal sum arrays
 sum_array = (n*(n+1))//2
 if sum_array%2 !=0:
  print(0)
  continue
 # 1 2 3 4 5 6 7 8 --  9 10 11 12  ---> divide closest to ideal sum

 n_swap = 0
 d = 1 + 4*sum_array
 partition_ind = (math.sqrt(d) - 1)/2
 n_swap = n - math.floor(partition_ind)
 f = math.factorial
 if partition_ind.is_integer():
  partition_ind = int(partition_ind)
  if partition_ind >= 2:
   n_swap += (f(partition_ind) // 2 // f(partition_ind-2))
  if n-partition_ind >= 2:
   n_swap += (f(n-partition_ind) // 2 // f(n-partition_ind-2))
   
 print(n_swap)


# cook your dish here
import math
t= int(input())
import operator as op
from functools import reduce

def ncr(n, r):
 r = min(r, n-r)
 numer = reduce(op.mul, list(range(n, n-r, -1)), 1)
 denom = reduce(op.mul, list(range(1, r+1)), 1)
 return numer // denom # or / in Python 2

for test in range(t):
 n = int(input())
 #If total sum is not even, then we cant divide array in 2 equal sum arrays
 sum_array = (n*(n+1))//2
 if sum_array%2 !=0:
  print(0)
  continue
 # 1 2 3 4 5 6 7 8 --  9 10 11 12  ---> divide closest to ideal sum
 ideal_sum = sum_array//2
 partition_sum = 0
 partition_ind = 0
 n_swap = 0
 for i in range(1,n+1):
  if i + partition_sum > ideal_sum:
   partition_ind = i-1
   break
  else:
   partition_sum += i
 n_swap = n - partition_ind
 f = math.factorial
 if partition_sum == ideal_sum:
  if partition_ind >= 2:
   n_swap += ncr(partition_ind,2)
  if n-partition_ind >= 2:
   n_swap += ncr(n-partition_ind,2)
   
 print(n_swap)


# cook your dish here
import math
t= int(input())
for test in range(t):
 n = int(input())
 #If total sum is not even, then we cant divide array in 2 equal sum arrays
 sum_array = (n*(n+1))//2
 if sum_array%2 !=0:
  print(0)
  continue
 # 1 2 3 4 5 6 7 8 --  9 10 11 12  ---> divide closest to ideal sum
 ideal_sum = sum_array//2
 partition_sum = 0
 partition_ind = 0
 n_swap = 0
 for i in range(1,n+1):
  if i + partition_sum > ideal_sum:
   partition_ind = i-1
   break
  else:
   partition_sum += i
 n_swap = n - partition_ind
 f = math.factorial
 if partition_sum == ideal_sum:
  if partition_ind >= 2:
   n_swap += (f(partition_ind) // 2 // f(partition_ind-2))
  if n-partition_ind >= 2:
   n_swap += (f(n-partition_ind) // 2 // f(n-partition_ind-2))
   
 print(n_swap)


import math
t=int(input())
for _ in range(t):
 n=int(input())
 d=n*(n+1)/4
 if n*(n+1)%4!=0:
  print("0")
 else:
  x=math.floor((-1+(math.sqrt(1+8*d)))//2)
  if x*(x+1)/2==3:
   print("2")
  elif x*(x+1)/2==d:
   print(n-x) + sum(range(x)) + sum(range(n-x))
  else:
   print(n-x)

# cook your dish here
from math import sqrt
for x in range(int(input())):
 N=int(input())
 sum=(N*(N+1))//2
 if sum%2!=0:
  print(0)
 else:
  m=(int((sqrt(1+4*(sum)))-1)//2)
  if(m*(m+1)//2==sum//2):
   print((((m-1)*m)//2)+N-m+((N-m-1)*(N-m))//2)
  else:
   print(N-m)

# cook your dish here
T=int(input())
while(T>0):
 T-=1
 N=int(input())
 Sum=N*(N+1)//2
 if Sum%2!=0:
  print("0")
 else:
  x=-1+(1+(4*Sum))**0.5
  x=x//2
  m=int(x)
  t=N-m
  left=(m*(m+1))//2
  right=(((N*(N+1))//2)-left)
  if left==right:
   r=N-m
   r=r-1
   m=m-1
   t+=(m*(m+1))//2
   t+=r*(r+1)//2
  print(t)


import math

def comb(n):
 return n*(n-1)//2
 
t = int(input())
while(t > 0):
 ans = 0
 n = int(input())
 total = n*(n+1)>>1
 if(total & 1 == 0):
  pivot = math.floor((-1+math.sqrt(1 + 4 * total))/2)
  ans += n - pivot
  if((pivot*(pivot+1))>>1 == total>>1):
   ans += comb(pivot) + comb(n-pivot)
   
 print(ans)
 t-=1

import math
 
t = int(input())
while(t > 0):
 ans = 0
 n = int(input())
 total = n*(n+1)>>1
 if(total & 1 == 0):
  pivot = math.floor((-1+math.sqrt(1 + 4 * total))/2)
  ans += n - pivot
  if((pivot*(pivot+1))>>1 == total>>1):
   ans += math.factorial(pivot)//(math.factorial(pivot-2) * 2)
   if(n-pivot > 1):
    ans += math.factorial(n-pivot)//(math.factorial(n-pivot-2) * 2)
 print(ans)
 t-=1