You are given an integer sequence $A_1, A_2, \ldots, A_N$ and an integer $X$. Consider a $N \times N$ matrix $B$, where $B_{i,j} = A_i + A_j$ for each valid $i$ and $j$.
You need to find the number of square submatrices of $B$ such that the sum of their elements is $X$. Formally, find the number of quartets $(x_1, y_1, x_2, y_2)$ such that $1 \le x_1 \le x_2 \le N$, $1 \le y_1 \le y_2 \le N$, $x_2-x_1 = y_2-y_1$ and $\sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2} B_{i,j} = X$.
-----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 line of each test case contains two space-separated integers $N$ and $X$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.
-----Output-----
For each test case, print a single line containing one integer ― the number of square submatrices with sum $X$.
-----Constraints-----
- $1 \le T \le 100$
- $1 \le X \le 10^6$
- $1 \le N \le 10^5$
- $1 \le A_i \le 10^6$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $10^6$
-----Subtasks-----
Subtask #1 (50 points): the sum of $N$ over all test cases does not exceed $1,000$
Subtask #2 (50 points): original constraints
-----Example Input-----
2
5 36
1 2 3 1 12
4 54
3 3 3 3
-----Example Output-----
6
4
def binary_search(b,item,n):
 lb = 0
 a = b[:]
 ub = n-1
 cnt = 1
 f = 0
 while lb<=ub:
  mid = (lb+ub)//2
  if a[mid] == item:
   f = 1
   a.pop(mid)
   ub = ub - 1
   cnt = cnt + 1
  elif a[mid] > item:
   ub = mid - 1
  else:
   lb = mid + 1

 if f == 1:
  return cnt
 else:
  return False


cases = int(input())
for v in range(cases):
 a = list(map(int,input().strip().split()))
 n = a[0]
 x = a[1]
 a = list(map(int,input().strip().split()))
 
 cnt = 0

 for i in range(1,n+1):
  if x%i == 0:
   side = i
   freq = 0
   subsetsum = []
   left = 0
   right = i-1
   s = sum(a[:right+1])
   if s > x:
    freq = freq + 1
   else:
    subsetsum.append(s)
   while right < n - 1:
    right += 1
    s = s + a[right] - a[left]
    left += 1
    
    if s > x:
     freq = freq + 1
    else:
     subsetsum.append(s)
    
   y = x//side
   subsetsum.sort()
   
   for r in range(n-side+1-freq):
    h = binary_search(subsetsum,y-subsetsum[r],n-side+1-freq)
    if h:
     cnt = cnt + h-1
    


 print(cnt)
   
    
# a = [1,2,3,4,5]
# n = 5
# for i in range(1,6):
#     print(i)
#     left = 0
#     right = i-1
#     subset = []
#     s = sum(a[:right+1])
#     subset.append(s)
#     while right < n-1:
#         right += 1
#         s = s + a[right] - a[left]
#         left += 1
#         subset.append(s)

#     print(subset)

def binary_search(b,item,n):
 lb = 0
 a = b[:]
 ub = n-1
 cnt = 1
 f = 0
 while lb<=ub:
  mid = (lb+ub)//2
  if a[mid] == item:
   f = 1
   a.pop(mid)
   ub = ub - 1
   cnt = cnt + 1
  elif a[mid] > item:
   ub = mid - 1
  else:
   lb = mid + 1

 if f == 1:
  return cnt
 else:
  return False


cases = int(input())
for v in range(cases):
 a = list(map(int,input().strip().split()))
 n = a[0]
 x = a[1]
 a = list(map(int,input().strip().split()))
 
 cnt = 0

 for i in range(1,n+1):
  if x%i == 0:
   side = i
   freq = 0
   subsetsum = []
   left = 0
   right = i-1
   s = sum(a[:right+1])
   if s > x:
    freq = freq + 1
   else:
    subsetsum.append(s)
   while right < n - 1:
    right += 1
    s = s + a[right] - a[left]
    left += 1
    
    if s > x:
     freq = freq + 1
    else:
     subsetsum.append(s)
    
   y = x//side
   subsetsum.sort()
   
   for r in range(n-side+1-freq):
    h = binary_search(subsetsum,y-subsetsum[r],n-side+1-freq)
    if h:
     cnt = cnt + h-1
    


 print(cnt)
   
    
# a = [1,2,3,4,5]
# n = 5
# for i in range(1,6):
#     print(i)
#     left = 0
#     right = i-1
#     subset = []
#     s = sum(a[:right+1])
#     subset.append(s)
#     while right < n-1:
#         right += 1
#         s = s + a[right] - a[left]
#         left += 1
#         subset.append(s)

#     print(subset)
