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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, x) = list(map(int, input().split()))
	l = [0]
	pre = [0] * (n + 1)
	sum = 0
	i = 1
	for m in input().split():
		l.append(int(m))
		sum += int(m)
		pre[i] = sum
		i += 1
	dict = {}
	k = []
	i = 1
	while i * i <= x:
		if x % i == 0:
			k.append(i)
			if i * i != x:
				k.append(x // i)
			else:
				break
		i += 1
	ans = 0
	for a in k:
		if a > n:
			continue
		z = x // a
		for j in range(a, n + 1):
			s = pre[j] - pre[j - a]
			if s > z:
				continue
			if s in dict:
				dict[s] += 1
			else:
				dict[s] = 1
		for j in range(a, n + 1):
			s = pre[j] - pre[j - a]
			if s > z:
				continue
			if z - s in dict:
				ans += dict[z - s]
		for j in range(a, n + 1):
			s = pre[j] - pre[j - a]
			if s > z:
				continue
			dict[s] = 0
	print(ans)


for _ in range(int(input())):
	(n, X) = map(int, input().split())
	b = list(map(int, input().split()))
	a = [[0 for j in range(n + 1)] for k in range(n + 1)]
	for i in range(n):
		for j in range(n):
			a[i + 1][j + 1] = b[i] + b[j]
	c = 0
	for i in range(n + 1):
		for j in range(n + 1):
			if i > 0:
				a[i][j] += a[i - 1][j]
			if j > 0:
				a[i][j] += a[i][j - 1]
			if i > 0 and j > 0:
				a[i][j] -= a[i - 1][j - 1]
			ii = i - 1
			jj = j - 1
			while ii > -1 and jj > -1:
				if a[i][j] - a[ii][j] - a[i][jj] + a[ii][jj] == X:
					c += 1
				ii -= 1
				jj -= 1
	print(c)


import math
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	count = 0
	y = dict()
	for i in range(n):
		if y.get(a[i]):
			y[a[i]] += 1
		else:
			y[a[i]] = 1
	for i in range(n):
		if a[i] >= x:
			pass
		else:
			p = x - a[i]
			if y.get(p):
				count += y[p]
			else:
				pass
	p = math.sqrt(x)
	if n < p:
		p = n
	b = []
	k = 2
	while k <= p:
		if x % k == 0:
			b.append(k)
		k += 1
	for i in b:
		summ = 0
		for j in range(i):
			summ += a[j]
		c = [summ]
		p = 0
		for j in range(i, n):
			summ += a[j]
			summ -= a[p]
			p += 1
			c.append(summ)
		l = len(c)
		y = dict()
		for j in range(l):
			if y.get(c[j]):
				y[c[j]] += 1
			else:
				y[c[j]] = 1
		for j in range(l):
			if c[j] >= x // i:
				pass
			else:
				p = x // i - c[j]
				if y.get(p):
					count += y[p]
				else:
					pass
	print(count)


import math
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	count = 0
	y = a.copy()
	y.sort()
	for i in range(n):
		if y[i] >= x:
			break
		else:
			p = x - y[i]
			u = 0
			v = n - 1
			cond = 0
			q = 0
			while u <= v:
				q = (u + v) // 2
				if y[q] > p:
					v = q - 1
				elif y[q] < p:
					u = q + 1
				else:
					cond = 1
					count += 1
					break
			if cond == 1:
				r = q
				s = q
				while r > 0:
					if y[r - 1] == y[r]:
						count += 1
						r -= 1
					else:
						break
				while s < n - 1:
					if y[s] == y[s + 1]:
						count += 1
						s += 1
					else:
						break
	p = math.sqrt(x)
	if n < p:
		p = n
	b = []
	k = 2
	while k <= p:
		if x % k == 0:
			b.append(k)
		k += 1
	po = 0
	pot = 0
	for i in b:
		summ = pot
		for j in range(po, i):
			summ += a[j]
		po = i
		pot = summ
		c = [summ]
		p = 0
		for j in range(i, n):
			summ += a[j]
			summ -= a[p]
			p += 1
			c.append(summ)
		c.sort()
		l = len(c)
		for t in range(l):
			if c[t] >= x // i:
				break
			else:
				p = x // i - c[t]
				u = 0
				v = l - 1
				cond = 0
				q = 0
				while u <= v:
					q = (u + v) // 2
					if c[q] > p:
						v = q - 1
					elif c[q] < p:
						u = q + 1
					else:
						cond = 1
						count += 1
						break
				if cond == 1:
					r = q
					s = q
					while r > 0:
						if c[r - 1] == c[r]:
							count += 1
							r -= 1
						else:
							break
					while s < l - 1:
						if c[s] == c[s + 1]:
							count += 1
							s += 1
						else:
							break
	print(count)


from datetime import datetime

class dicta(dict):

	def __init__(self, *args, **kwargs):
		super(dicta, self).__init__(*args, **kwargs)
		self.__dict__ = self
START_TIME = datetime.now()

def debug(**kwargs):
	return
	diff = str(datetime.now() - START_TIME)
	for (key, value) in list(kwargs.items()):
		if isinstance(value, list):
			print(diff, key + ':')
			for (itemKey, item) in enumerate(value):
				print('\t\t\t', str(itemKey) + ': ' + str(item))
		elif isinstance(value, dict):
			print(diff, key + ':')
			for (itemKey, item) in list(value.items()):
				print('\t\t\t', itemKey + ': ' + str(item))
		else:
			print(diff, key + ': ' + str(value))

def printResult(result):
	if isinstance(result, list):
		print(*result)
	else:
		print(result)

def main():
	debug(status='started')
	noOfTests = int(input())
	for i in range(noOfTests):
		result = runATest(i)
		if isinstance(result, tuple):
			for line in result:
				printResult(line)
		else:
			printResult(result)
		if noOfTests > 1:
			debug(status='-------------------- finished Test#' + str(i + 1) + ' \xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0--------------------')
	debug(status='finished')

def runATest(_testIndex):
	[count, refTotal] = [int(x) for x in input().split()]
	aList = [int(x) for x in input().split()]
	factors = findFactors(refTotal, count)
	total = 0
	for factor in factors:
		total += countSquaresOfSize(aList, refTotal, count, factor)
	return total

def findFactors(refTotal, maxFactor):
	outList = [1]
	for i in range(2, int(refTotal / 2) + 1):
		if i > maxFactor:
			break
		if refTotal % i == 0:
			outList.append(i)
	if refTotal <= maxFactor:
		outList.append(refTotal)
	return outList

def countSquaresOfSize(aList, refTotal, count, size):
	reqSum = int(refTotal / size)
	sumList = [0] * (reqSum + 1)
	sumSize = sum(aList[:size])
	if sumSize <= reqSum:
		sumList[sumSize] += 1
	debug()
	rightOffset = size - 1
	for i in range(1, count + 1 - size):
		sumSize = sumSize - aList[i - 1] + aList[i + rightOffset]
		if sumSize <= reqSum:
			sumList[sumSize] += 1
	total = 0
	for i in range(0, (reqSum + 1) // 2 + 1):
		subTotal = sumList[i] * sumList[-1 - i]
		if i != reqSum - i:
			subTotal *= 2
		total += subTotal
	debug(reqSum=reqSum, size=size, total=total, sumList=sumList)
	return total
main()


from sys import stdin, stdout
import numpy as np

def main():
	for _ in range(int(stdin.readline())):
		(N, X) = list(map(int, stdin.readline().split()))
		array = np.array(list(map(int, stdin.readline().split()))).reshape(N, 1)
		count = 0
		adsum = 0
		sum = 0
		valid = list([x for x in range(1, N + 1) if (X / x).is_integer()])
		for length in valid:
			for j in range(N - length + 1):
				sum = np.sum(array[j:j + length]) * length
				for k in range(N - length + 1):
					adsum = length * np.sum(array[k:k + length])
					if sum + adsum == X:
						count += 1
		print(count)

def __starting_point():
	main()
__starting_point()


from datetime import datetime
START_TIME = datetime.now()

def debug(*args, **kwargs):
	return

def printResult(result):
	if isinstance(result, list):
		print(*result)
	else:
		print(result)

def main():
	debug('started')
	noOfTests = int(input())
	for i in range(noOfTests):
		result = runATest(i)
		if isinstance(result, tuple):
			for line in result:
				printResult(line)
		else:
			printResult(result)
	debug('finished')

def runATest(_testIndex):
	[count, refTotal] = [int(x) for x in input().split()]
	aList = [int(x) for x in input().split()]
	factors = findFactors(refTotal, count)
	debug(factors=factors)
	total = 0
	for factor in factors:
		total += countSquaresOfSize(aList, refTotal, count, factor)
	return total

def findFactors(refTotal, maxFactor):
	outList = [1]
	for i in range(2, int(refTotal / 2) + 1):
		if i > maxFactor:
			break
		if refTotal % i == 0:
			outList.append(i)
	if refTotal <= maxFactor:
		outList.append(refTotal)
	return outList

def countSquaresOfSize(aList, refTotal, count, size):
	reqTotal = int(refTotal / size)
	maxLen = count + 1 - size
	total = 0
	for i in range(maxLen):
		for j in range(maxLen):
			if countSquaresAtPointOfSize(aList, reqTotal, size, i, j):
				total += 1
	debug('completed size', size=size, total=total)
	return total

def countSquaresAtPointOfSize(aList, reqTotal, size, i, j):
	total = 0
	for k in range(size):
		total += aList[i + k] + aList[j + k]
	debug(i=i, j=j, size=size, total=total, reqTotal=reqTotal)
	return total == reqTotal
main()


from math import sqrt
t = int(input())

def get_factors(x):
	factors = [1]
	for i in range(2, int(sqrt(x)) + 1):
		if k % i == 0:
			factors.append(i)
	factors.append(x)
	return factors
for _ in range(t):
	(n, k) = list([int(x) for x in input().split()])
	a = list([int(x) for x in input().split()])
	factors = get_factors(k)
	total = 0
	for factor in factors:
		if factor > len(a):
			break
		freq = {}
		sliding_window = a[0:factor]
		s = sum(sliding_window)
		freq[s] = 1
		for i in range(factor, len(a)):
			sliding_window = sliding_window[1:] + [a[i]]
			s = sum(sliding_window)
			if s > k / factor:
				continue
			if s not in freq:
				freq[s] = 0
			freq[s] += 1
		for s in freq:
			total += freq.get(k // factor - s, 0) * freq[s]
	print(total)


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)


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)
			for r in range(n - side + 1 - freq):
				for c in range(n - side + 1 - freq):
					if subsetsum[r] + subsetsum[c] == x // side:
						cnt += 1
	print(cnt)


try:
	import math
	from collections import defaultdict
	from sys import stdin
	for _ in range(int(stdin.readline())):
		(n, x) = list(map(int, stdin.readline().strip().split()))
		list1 = list(map(int, stdin.readline().strip().split()))
		ll = set()
		for i in range(1, n):
			list1[i] = list1[i] + list1[i - 1]
		c = 0
		for i in range(1, n + 1):
			if x % i == 0:
				a = i
				y = x // a
				list2 = [0] * (y + 1)
				j = -1
				dict1 = {}
				for i in range(a - 1, n):
					if j == -1:
						if list1[i] <= y:
							list2[list1[i]] += 1
						j += 1
					else:
						if list1[i] - list1[j] <= y:
							list2[list1[i] - list1[j]] += 1
						j += 1
				j = -1
				for i in range(a - 1, n):
					if j == -1:
						if list1[i] <= y:
							c += list2[y - list1[i]]
						j += 1
					else:
						if list1[i] - list1[j] <= y:
							if list1[i] - list1[j] <= y:
								c += list2[y - (list1[i] - list1[j])]
						j += 1
		print(c)
except:
	pass


try:
	import math
	from collections import defaultdict
	for _ in range(int(input())):
		(n, x) = list(map(int, input().split()))
		list1 = list(map(int, input().split()))
		ll = set()
		for i in range(1, int(math.sqrt(x)) + 1):
			if x % i == 0:
				if i <= n:
					ll.add(i)
				if x // i <= n:
					ll.add(x // i)
		for i in range(1, n):
			list1[i] = list1[i] + list1[i - 1]
		c = 0
		for i in ll:
			a = i
			y = x // a
			list2 = []
			j = -1
			dict1 = {}
			for i in range(a - 1, n):
				if j == -1:
					list2.append(list1[i])
					if list1[i] in dict1:
						dict1[list1[i]] += 1
					else:
						dict1[list1[i]] = 1
					j += 1
				else:
					list2.append(list1[i] - list1[j])
					if list1[i] - list1[j] in dict1:
						dict1[list1[i] - list1[j]] += 1
					else:
						dict1[list1[i] - list1[j]] = 1
					j += 1
			for k in list2:
				if y - k in dict1:
					c += dict1[y - k]
		print(c)
except:
	pass


import math
t = int(input())
while t != 0:
	t -= 1
	ans = 0
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	a = []
	a.append(0)
	for i in range(n):
		a.append(l[i] + a[i])
	for i in range(1, int(math.sqrt(x) + 1)):
		if x % i is 0:
			y = x / i
			m = {}
			for j in range(i, n + 1):
				if a[j] - a[j - i] in m:
					m[a[j] - a[j - i]] += 1
				else:
					m[a[j] - a[j - i]] = 1
			for j in range(i, n + 1):
				z = y - (a[j] - a[j - i])
				if z in m:
					if a[j] - a[j - i] == z:
						ans += m[a[j] - a[j - i]] * m[z]
						m[z] = 0
					else:
						ans += m[a[j] - a[j - i]] * m[z] * 2
						m[a[j] - a[j - i]] = 0
						m[z] = 0
	print(ans)


def main():
	T = int(input())
	for _ in range(T):
		(N, X) = map(int, input().split())
		A = [0] + list(map(int, input().split()))
		factorsList = []
		i = 1
		ans = 0
		while i * i <= X:
			if X % i == 0:
				factorsList.append(i)
				if i != X // i:
					factorsList.append(X // i)
			i += 1
		prefixSums = [0]
		for i in range(1, N + 1):
			prefixSums.append(prefixSums[i - 1] + A[i])
		for factor in factorsList:
			if factor > N:
				continue
			summRequired = X // factor
			d = {}
			for i in range(factor, N + 1):
				s = prefixSums[i] - prefixSums[i - factor]
				if s <= summRequired:
					if s not in d:
						d[s] = 1
					else:
						d[s] += 1
			for i in range(factor, N + 1):
				s = prefixSums[i] - prefixSums[i - factor]
				if s <= summRequired:
					if summRequired - s in d:
						ans += d[summRequired - s]
		print(ans)

def __starting_point():
	main()
__starting_point()