Given a sorted linked list of distinct nodes (no two nodes have the same data) and an integer X. Count distinct triplets in the list that sum up to given integer X.
Note: The Linked List can be sorted in any order.
Example 1:
Input: LinkedList: 1->2->4->5->6->8->9, X = 17
Output: 2
Explanation: Distinct triplets are (2, 6, 9) 
and (4, 5, 8) which have sum equal to X i.e 17.
Example 2:
Input: LinkedList: 1->2->4->5->6->8->9, X = 15
Output: 5
Explanation: (1, 5, 9), (1, 6, 8), (2, 4, 9), 
(2, 5, 8), (4, 5, 6) are the distinct triplets
Your Task:  
You don't need to read input or print anything. Complete the function countTriplets() which takes a head reference and X as input parameters and returns the triplet count
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ Number of Nodes ≤ 10^{3} 
1 ≤ Node value ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Mathematics

Starter code: #User function Template for python3

def countTriplets(head,x):
    # code here

Solutions:
def countTriplets(head, x):
	if head == None:
		return
	temp1 = head
	answer = []
	while temp1:
		hashmap = {}
		temp2 = temp1.nxt
		while temp2:
			value = x - (temp1.val + temp2.val)
			if value in hashmap:
				answer.append([temp1.val, temp2.val, value])
			else:
				hashmap[temp2.val] = 1
			temp2 = temp2.nxt
		temp1 = temp1.nxt
	return len(answer)


def countTriplets(head, x):
	arr = []
	while head:
		arr.append(head.val)
		head = head.nxt
	count = 0
	d = {}
	for i in range(len(arr)):
		d[arr[i]] = i
	for i in range(len(arr)):
		for j in range(i + 1, len(arr)):
			k = x - (arr[i] + arr[j])
			if k in d and d[k] != i and (d[k] != j):
				count += 1
	return count // 3


def countTriplets(head, x):
	h1 = head
	count = 0
	while h1:
		m = {}
		h2 = h1.nxt
		while h2:
			value = x - (h1.val + h2.val)
			if value in m:
				count += 1
			else:
				m[h2.val] = 1
			h2 = h2.nxt
		h1 = h1.nxt
	return count


def countTriplets(head, x):
	curr1 = head
	answer = []
	while curr1:
		hashmap = {}
		curr2 = curr1.nxt
		while curr2:
			value = x - (curr1.val + curr2.val)
			if value in hashmap:
				answer.append([curr1.val, curr2.val, value])
			else:
				hashmap[curr2.val] = 1
			curr2 = curr2.nxt
		curr1 = curr1.nxt
	return len(answer)


def countTriplets(head, x):
	temp = head
	c = 0
	while temp.nxt.nxt:
		s = set()
		f = temp.val
		s.add(temp.nxt.val)
		k = temp.nxt.nxt
		while k:
			if x - (k.val + f) in s:
				c += 1
			else:
				s.add(k.val)
			k = k.nxt
		temp = temp.nxt
	return c


def countTriplets(head, x):
	l = []
	temp = head
	while temp != None:
		l.append(temp.val)
		temp = temp.nxt
	n = len(l)
	l.sort()
	c = 0
	for i in range(n - 2):
		le = i + 1
		r = n - 1
		while le < r:
			s = l[i] + l[le] + l[r]
			if s == x:
				c += 1
				le += 1
				r -= 1
			elif s < x:
				le = le + 1
			else:
				r = r - 1
	return c


def countTriplets(head, x):
	curr = head
	l = []
	ans = 0
	while curr:
		l.append(curr.val)
		curr = curr.nxt
	l.sort()
	n = len(l)
	for i in range(n - 2):
		m = i + 1
		r = n - 1
		while m < r:
			if l[i] + l[m] + l[r] == x:
				ans += 1
				m += 1
				r = r - 1
			elif l[i] + l[m] + l[r] > x:
				r -= 1
			else:
				m += 1
	return ans


def countTriplets(head, x):
	lst = []
	itr = head
	while itr:
		lst.append(itr.val)
		itr = itr.nxt
	count = 0
	for i in range(len(lst)):
		l = i + 1
		r = len(lst) - 1
		while l < r:
			if lst[i] < lst[l]:
				if lst[i] + lst[l] + lst[r] == x:
					count += 1
					l += 1
					r -= 1
				elif lst[i] + lst[l] + lst[r] > x:
					r -= 1
				else:
					l += 1
			elif lst[i] + lst[l] + lst[r] == x:
				count += 1
				l += 1
				r -= 1
			elif lst[i] + lst[l] + lst[r] < x:
				r -= 1
			else:
				l += 1
	return count


def countTriplets(head, x):
	dic = {}
	tt = head
	while tt:
		dic[tt.val] = tt
		tt = tt.nxt
	c = 0
	temp = head
	while temp:
		tmp = temp.nxt
		while tmp:
			s = temp.val + tmp.val
			if x - s in dic and dic[x - s] != temp and (dic[x - s] != tmp):
				c += 1
			tmp = tmp.nxt
		temp = temp.nxt
	return c // 3


def countTriplets(head, x):
	dicti = {}
	z = head
	kk = 0
	p = 0
	while z != None:
		dicti[z.val] = p
		p = p + 1
		z = z.nxt
	p1 = head
	p2 = head.nxt
	while p1 != None:
		while p2 != None:
			u = x - p1.val - p2.val
			if u in dicti.keys() and u != p1.val and (u != p2.val) and (dicti[u] > dicti[p1.val]) and (dicti[u] > dicti[p2.val]):
				kk = kk + 1
			p2 = p2.nxt
		p1 = p1.nxt
		if p1.nxt == None:
			break
		p2 = p1.nxt
	return kk


def countTriplets(head, x):
	z = []
	while head is not None:
		z.append(head.val)
		head = head.nxt
	c = 0
	z.sort()
	k = len(z)
	for i in range(k - 2):
		l = i + 1
		h = k - 1
		while l < h:
			if z[i] + z[l] + z[h] == x:
				c = c + 1
				l = l + 1
				h = h - 1
			elif z[i] + z[l] + z[h] < x:
				l = l + 1
			else:
				h = h - 1
	return c


def countTriplets(head, x):
	values = []
	while head is not None:
		values.append(head.val)
		head = head.nxt
	count = 0
	values.sort()
	n = len(values)
	for i in range(n - 2):
		j = i + 1
		k = n - 1
		while j < k:
			if values[i] + values[j] + values[k] == x:
				count += 1
				j += 1
				k -= 1
			elif values[i] + values[j] + values[k] < x:
				j += 1
			else:
				k -= 1
	return count


def countTriplets(head, x):
	if not head or not head.nxt:
		return 0
	count = 0
	arr = []
	curr = head
	while curr:
		arr.append(curr.val)
		curr = curr.nxt
	n = len(arr)
	arr.sort()
	for start in range(n - 2):
		mid = start + 1
		end = n - 1
		while mid < end:
			Sum = arr[start] + arr[mid] + arr[end]
			if Sum == x:
				count += 1
				mid += 1
				end -= 1
			elif Sum > x:
				end -= 1
			else:
				mid += 1
	return count


def countTriplets(head, X):
	l = []
	while head:
		l.append(head.val)
		head = head.nxt
	l.sort()
	n = len(l)
	ans = 0
	for i in range(n):
		req = X - l[i]
		(x, y) = (i + 1, n - 1)
		while x < y:
			if l[x] + l[y] == req:
				ans += 1
				x += 1
				y -= 1
			elif l[x] + l[y] > req:
				y -= 1
			else:
				x += 1
	return ans


def countTriplets(head, x):
	l = []
	while head:
		l.append(head.val)
		head = head.nxt
	l.sort()
	ans = 0
	n = len(l)
	for i in range(n):
		t = x - l[i]
		left = i + 1
		right = n - 1
		while left < right:
			current = l[left] + l[right]
			if current < t:
				left += 1
			elif current > t:
				right -= 1
			else:
				ans += 1
				left += 1
	return ans


def countTriplets(head, x):
	P = []
	while head:
		P.append(head.val)
		head = head.nxt
	P.sort()
	count = 0
	for i in range(len(P) - 2):
		j = i + 1
		k = n - 1
		while j < k:
			S = P[i] + P[j] + P[k]
			if S > x:
				k -= 1
			elif S < x:
				j += 1
			else:
				count += 1
				j += 1
				k -= 1
	return count


def countTriplets(head, x):
	count = 0
	while head.nxt != None:
		d = {}
		temp = head.nxt
		while temp != None:
			if x - (temp.val + head.val) in d.keys():
				count += 1
			else:
				d[temp.val] = 1
			temp = temp.nxt
		head = head.nxt
	return count


def countTriplets(head, x):
	arr = []
	curr = head
	while curr:
		arr.append(curr.val)
		curr = curr.nxt
	ans = 0
	arr.sort()
	for i in range(len(arr)):
		low = i + 1
		high = len(arr) - 1
		while low < high:
			if arr[i] + arr[low] + arr[high] == x:
				ans += 1
				low += 1
			elif arr[i] + arr[low] + arr[high] < x:
				low += 1
			else:
				high -= 1
	return ans


def countTriplets(start, x):
	temp = start
	l = []
	while temp:
		l.append(temp.val)
		temp = temp.nxt
	l.sort()
	c = 0
	for i in range(0, n - 2):
		j = i + 1
		k = len(l) - 1
		while j < k:
			if l[i] + l[j] + l[k] == x:
				c += 1
				j += 1
				k -= 1
			elif l[i] + l[j] + l[k] > x:
				k -= 1
			else:
				j += 1
	return c


def countTriplets(start, x):
	arr = []
	temp = start
	while temp:
		arr.append(temp.val)
		temp = temp.nxt
	result = 0
	arr.sort()
	for i in range(len(arr) - 2):
		j = i + 1
		k = len(arr) - 1
		while j < k:
			if arr[i] + arr[j] + arr[k] < x:
				j += 1
			elif arr[i] + arr[j] + arr[k] > x:
				k -= 1
			else:
				result += 1
				j += 1
	return result


class Node:

	def __init__(self, x):
		self.val = x
		self.nxt = None
		self.prev = None

def countTriplets(head, x):
	if not head:
		return
	prev = None
	cur = head
	while cur:
		nxt = cur.nxt
		cur.prev = prev
		prev = cur
		cur = nxt
	tail = prev
	count = 0
	cur = head
	while cur.nxt:
		diff = x - cur.val
		start = cur.nxt
		end = tail
		while start and end and (start != end):
			if start.val + end.val == diff:
				count += 1
				end = end.prev
			elif start.val + end.val < diff:
				end = end.prev
			elif start.val + end.val > diff:
				start = start.nxt
		cur = cur.nxt
	return count


def countTriplets(head, x):
	lis = []
	itr = head
	while itr:
		lis.append(itr.val)
		itr = itr.nxt
	dic = {}
	for i in lis:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
	lis.sort()
	ans = 0
	for i in range(len(lis) - 2):
		m = i + 1
		r = len(lis) - 1
		while m < r:
			if lis[i] + lis[m] + lis[r] == x:
				ans += 1
				m += 1
				r -= 1
			elif lis[i] + lis[m] + lis[r] > x:
				r -= 1
			else:
				m += 1
	return ans


def countTriplets(head, x):
	c = 0
	num = []
	t = head
	while t:
		num.append(t.val)
		t = t.nxt
	num.sort()
	for i in range(len(num) - 2):
		l = i + 1
		r = len(num) - 1
		while l < r:
			k = num[i] + num[l] + num[r]
			if k == x:
				c += 1
				l += 1
				r -= 1
			elif k > x:
				r -= 1
			else:
				l += 1
	return c


def countTriplets(head, key):

	def reverse(head):
		cur = head
		prev = None
		while cur:
			nxt = cur.nxt
			cur.nxt = prev
			prev = cur
			cur = nxt
		head = prev
		return head
	p = head
	head2 = Node(0)
	ans = head2
	q = head
	while q:
		head2.nxt = Node(q.val)
		head2 = head2.nxt
		q = q.nxt
	right = reverse(ans.nxt)
	count = 0
	while p.nxt:
		q = p.nxt
		r = right
		while q and r and (q.val != r.val):
			value = p.val + q.val + r.val
			if value == key:
				count += 1
				q = q.nxt
			elif value < key:
				r = r.nxt
			else:
				q = q.nxt
		p = p.nxt
	return count


def countTriplets(head, x):
	nums = []
	t = head
	while t:
		nums.append(t.val)
		t = t.nxt
	count = 0
	di = {}
	i = 0
	while i < n - 2:
		temp = x - nums[i]
		dic = {}
		for j in range(i + 1, n):
			if temp - nums[j] in dic:
				count += 1
			dic[nums[j]] = 1
		i += 1
	return count


def count(head):
	n = head
	count = 0
	while n:
		count += 1
		n = n.next

def countTriplets(head, x):
	node = head
	list = []
	while node:
		list.append(node.val)
		node = node.nxt
	N = len(list)
	k = N - 1
	if list[0] > list[1]:
		list.sort()
	count = 0
	while k >= 2:
		j = k - 1
		i = 0
		while i < j:
			if list[i] + list[j] + list[k] == x:
				count += 1
				i += 1
				j -= 1
			elif list[i] + list[j] + list[k] > x:
				j -= 1
			else:
				i += 1
		k -= 1
	return count


def countTriplets(head, x):
	ans = 0
	arr = []
	p = head
	while p:
		arr.append(p.val)
		p = p.nxt
	for i in range(len(arr)):
		remaining = x - arr[i]
		d = {}
		for j in range(i + 1, len(arr)):
			if arr[j] in d:
				ans += 1
			else:
				d[remaining - arr[j]] = j
	return ans


def countTriplets(head, x):
	ans = 0
	arr = []
	p = head
	while p:
		arr.append(p.val)
		p = p.nxt
	arr.sort()
	for i in range(len(arr)):
		l = i + 1
		r = len(arr) - 1
		while l < r:
			c = arr[i] + arr[l] + arr[r]
			if c == x:
				ans += 1
				l += 1
				r -= 1
			elif c < x:
				l += 1
			else:
				r -= 1
	return ans


def countTriplets(head, x):
	nums = []
	t = head
	while t:
		nums.append(t.val)
		t = t.nxt
	nums.sort()
	if n == 1:
		return []
	brr = []
	di = {}
	i = 0
	while i < n - 2:
		temp = x - nums[i]
		dic = {}
		for j in range(i + 1, n):
			if temp - nums[j] in dic:
				mi = min(nums[i], nums[j], -(nums[i] + nums[j]))
				ma = max(nums[i], nums[j], -(nums[i] + nums[j]))
				sec = -(mi + ma)
				brr.append((mi, sec, ma))
			dic[nums[j]] = 1
		i += 1
	brr = list(set(brr))
	return len(brr)


def countTriplets(head, x):
	p = head
	l = []
	while p != None:
		l.append(p.val)
		p = p.nxt
	c = 0
	n = len(l)
	l.sort()
	for i in range(n - 2):
		j = i + 1
		k = n - 1
		while j < k:
			if l[i] + l[j] + l[k] == x:
				c += 1
				j += 1
				k -= 1
			elif l[i] + l[j] + l[k] < x:
				j += 1
			else:
				k -= 1
	return c


def countTriplets(head, x):
	arr = []
	while head:
		arr.append(head.val)
		head = head.nxt
	n = len(arr)
	cnt = 0
	ind = {}
	for i in range(len(arr)):
		ind[arr[i]] = i
	for i in range(n):
		for j in range(i + 1, n):
			if ind.get(x - arr[i] - arr[j], -1) != -1 and ind[x - arr[i] - arr[j]] > j:
				cnt += 1
	return cnt


def countTriplets(head, x):

	def traversal(head):
		n = head
		while n != None:
			list1.append(n.val)
			n = n.nxt
	list1 = []
	traversal(head)
	length = len(list1)
	count = 0
	list1.sort()
	for i in range(length - 2):
		j = i + 1
		k = length - 1
		while j < k:
			if list1[i] + list1[j] + list1[k] == x:
				count += 1
				j += 1
				k -= 1
			elif list1[i] + list1[j] + list1[k] > x:
				k -= 1
			elif list1[i] + list1[j] + list1[k] < x:
				j += 1
	return count


def countTriplets(head, x):
	c = head
	l = []
	while c:
		l.append(c.val)
		c = c.nxt
	res = 0
	l.sort()
	for i in range(n - 2):
		le = i + 1
		r = n - 1
		while le < r:
			if l[i] + l[le] + l[r] == x:
				res += 1
				le += 1
				r -= 1
			elif l[i] + l[le] + l[r] > x:
				r -= 1
			else:
				le += 1
	return res


def countTriplets(head, x):
	(arr, len1, res) = ([], 0, 0)
	while head:
		arr.append(head.val)
		(head, len1) = (head.nxt, len1 + 1)
	arr.sort()
	for i in range(len1 - 2):
		(start, end) = (i + 1, len1 - 1)
		sum1 = x - arr[i]
		while start < end:
			if arr[start] + arr[end] == sum1:
				(res, start, end) = (res + 1, start + 1, end - 1)
			elif arr[start] + arr[end] > sum1:
				end -= 1
			elif arr[start] + arr[end] < sum1:
				start += 1
	return res


def countTriplets(head, x):
	(L, K, M) = ([], [], [])
	temp = head
	while temp:
		a = temp.val
		L.append(a)
		temp = temp.nxt
	L.sort()
	count = 0
	for i in range(n - 2):
		(m, r) = (i + 1, n - 1)
		while m < r:
			if L[i] + L[m] + L[r] == x:
				(count, m, r) = (count + 1, m + 1, r - 1)
			elif L[i] + L[m] + L[r] > x:
				r -= 1
			else:
				m += 1
	return count


def countTriplets(head, x):
	map = []
	curr = head
	while curr is not None:
		map.append(curr.val)
		curr = curr.nxt
	c = 0
	map.sort()
	for i in range(len(map) - 2):
		start = i + 1
		end = len(map) - 1
		while start < end:
			if map[start] + map[end] + map[i] == x:
				c += 1
				start += 1
				end -= 1
			elif map[start] + map[end] + map[i] > x:
				end -= 1
			else:
				start += 1
	return c


def countTriplets(head, x):
	itemsArr = []
	itemsHT = {}
	while head is not None:
		nextVal = head.val
		itemsArr.append(nextVal)
		itemsHT[nextVal] = 1
		head = head.nxt
	arrayLen = len(itemsArr)
	result = 0
	for i in range(arrayLen - 1):
		for j in range(i + 1, arrayLen):
			itemToFind = x - itemsArr[i] - itemsArr[j]
			if itemToFind == itemsArr[i] or itemToFind == itemsArr[j]:
				continue
			elif itemToFind in itemsHT:
				result += 1
	return result // 3


def countTriplets(head, x):
	ans = 0
	dict1 = {}
	n = head
	while n:
		dict1[n.val] = 1
		n = n.nxt
	if head.val > head.nxt.val:
		curr = head
		prev = None
		while curr:
			nxt = curr.nxt
			curr.nxt = prev
			prev = curr
			curr = nxt
		head = prev
	n = head
	while n:
		m = n.nxt
		while m:
			ele = x - (m.val + n.val)
			if ele in dict1 and ele > m.val:
				ans += 1
			elif ele <= m.val:
				break
			m = m.nxt
		n = n.nxt
	return ans


def countTriplets(head, x):
	vv = []
	while head != None:
		vv.append(head.val)
		head = head.nxt
	ans = 0
	for i in range(len(vv) - 2):
		s = i + 1
		e = len(vv) - 1
		while s < e:
			temp = vv[i] + vv[s] + vv[e]
			if temp == x:
				ans += 1
				s += 1
				e -= 1
			elif temp > x:
				s += 1
			else:
				e -= 1
	return ans


def countTriplets(head, x):
	p = head
	arr = []
	count = 0
	while p:
		arr.append(p.val)
		p = p.nxt
	arr.sort()
	n = len(arr)
	for i in range(n - 2):
		target = x - arr[i]
		j = i + 1
		k = n - 1
		while j < k:
			sum = arr[j] + arr[k]
			if sum == target:
				count = count + 1
				j = j + 1
				k = k - 1
			elif sum < target:
				j = j + 1
			elif sum > target:
				k = k - 1
	return count


def countTriplets(head, x):
	l = []
	while head != None:
		l.append(head.val)
		head = head.nxt
	count = 0
	n = len(l)
	for i in range(0, n - 2):
		start = n - 1
		end = i + 1
		while start > end:
			if l[start] + l[end] == x - l[i]:
				count += 1
				start -= 1
				end += 1
			elif l[start] + l[end] > x - l[i]:
				end += 1
			else:
				start -= 1
	return count


def countTriplets(head, x):
	curr = head
	map = {}
	while curr:
		map[curr.val] = 1
		curr = curr.nxt
	curr = head
	count = 0
	while curr:
		next = curr.nxt
		while next:
			p_sum = int(next.val) + int(curr.val)
			if x - p_sum in map and x - p_sum != next.val and (x - p_sum != curr.val):
				count += 1
			next = next.nxt
		curr = curr.nxt
	return count // 3


def countTriplets(head, x):
	vals = list()
	while head:
		vals.append(head.val)
		head = head.nxt
	vals = sorted(vals)
	ans = set()
	n = len(vals)
	for i in range(n - 2):
		j = i + 1
		k = n - 1
		while j < k:
			new_sum = vals[i] + vals[j] + vals[k]
			if new_sum == x:
				ans.add((i, j, k))
				j += 1
				k -= 1
			elif new_sum > x:
				k -= 1
			else:
				j += 1
	return len(ans)


def countTriplets(head, x):
	curr = head
	l = []
	while curr != None:
		l.append(curr.val)
		curr = curr.nxt
	n = len(l)
	l.sort()
	ans = 0
	for i in range(n - 2):
		j = i + 1
		k = n - 1
		while j < k:
			sum1 = l[i] + l[j] + l[k]
			if sum1 == x:
				ans += 1
				j += 1
				k -= 1
			elif sum1 > x:
				k -= 1
			else:
				j += 1
	return ans


def countTriplets(head, x):
	lst = []
	count = 0
	temp = head
	while temp is not None:
		lst.append(temp.val)
		temp = temp.nxt
	lst.sort()
	i = 0
	while i < len(lst) - 2:
		j = i + 1
		k = len(lst) - 1
		while j < len(lst) - 1 and j < k:
			if lst[i] + lst[j] + lst[k] == x:
				count += 1
				j += 1
			elif lst[i] + lst[j] + lst[k] < x:
				j += 1
			else:
				k -= 1
		i += 1
	return count


def countTriplets(head, x):
	u = []
	t = head
	c = 0
	while t:
		u.append(t.val)
		t = t.nxt
	u = sorted(u)
	for i in range(len(u) - 2):
		l = i + 1
		r = len(u) - 1
		while l < r:
			if u[i] + u[l] + u[r] == x:
				c += 1
				l += 1
				r -= 1
			if u[i] + u[l] + u[r] > x:
				r = r - 1
			if u[i] + u[l] + u[r] < x:
				l += 1
	return c


def countTriplets(head, x):
	list1 = []
	while head:
		list1.append(head.val)
		head = head.nxt
	list1.sort()
	count = 0
	n = len(list1)
	for i in range(n - 2):
		l = i + 1
		r = n - 1
		while l < r:
			summ = list1[i] + list1[l] + list1[r]
			if summ == x:
				count += 1
				l += 1
				r -= 1
			elif summ < x:
				l += 1
			else:
				r -= 1
	return count


def countTriplets(head, x):
	l = list()
	curr = head
	while curr:
		l.append(curr.val)
		curr = curr.nxt
	l.sort()
	count = 0
	n = len(l)
	for i in range(n - 2):
		j = i + 1
		k = n - 1
		while j < k:
			if l[i] + l[j] + l[k] < x:
				j += 1
			elif l[i] + l[j] + l[k] > x:
				k -= 1
			else:
				count += 1
				j += 1
				k -= 1
	return count


def countTriplets(head, x):
	a = []
	itr = head
	count = 0
	while itr:
		a.append(itr.val)
		itr = itr.nxt
	a.sort()
	for i in range(len(a) - 2):
		start = i + 1
		end = len(a) - 1
		while start < end:
			if a[i] + a[start] + a[end] > x:
				end -= 1
			elif a[i] + a[start] + a[end] < x:
				start += 1
			else:
				count += 1
				start += 1
	return count


def countTriplets(head, x):
	d = []
	temp = head
	while temp:
		d.append(temp.val)
		temp = temp.nxt
	d.sort()
	cnt = 0
	for i in range(len(d) - 2):
		l = i + 1
		h = len(d) - 1
		while l < h:
			if d[i] + d[l] + d[h] == x:
				cnt += 1
				l += 1
			if d[i] + d[l] + d[h] < x:
				l += 1
			else:
				h -= 1
	return cnt


def countTriplets(head, x):
	d = {}
	v = []
	t = head
	while t != None:
		v.append(t.val)
		d[t.val] = len(v) - 1
		t = t.nxt
	count = 0
	for i in range(len(v)):
		o = x - v[i]
		for j in range(i + 1, len(v)):
			l = o - v[j]
			if d.get(l) and d[l] > j:
				count += 1
	return count


def countTriplets(head, x):
	d = []
	temp = head
	while temp:
		d.append(temp.val)
		temp = temp.nxt
	d.sort()
	cnt = 0
	for i in range(len(d) - 2):
		l = i + 1
		h = len(d) - 1
		while l < h:
			if d[i] + d[l] + d[h] == x:
				cnt += 1
				l += 1
			if d[i] + d[l] + d[h] < x:
				l += 1
			else:
				h -= 1
	return cnt

class Node:

	def __init__(self, x):
		self.val = x
		self.nxt = None
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		line = input().strip().split()
		n = int(line[0])
		x = int(line[1])
		line = input().strip().split()
		head = Node(int(line[0]))
		tail = head
		for i in range(1, n):
			tail.nxt = Node(int(line[i]))
			tail = tail.nxt
		print(countTriplets(head, x))


def countTriplets(head, x):
	dec = {}
	one = head
	while one:
		dec[one.val] = 1
		one = one.nxt
	count = 0
	two = head
	while two:
		three = two.nxt
		while three:
			want = x - two.val - three.val
			if want == two.val or want == three.val:
				three = three.nxt
				continue
			if dec.get(want):
				count += 1
			three = three.nxt
		two = two.nxt
	return count // 3

class Node:

	def __init__(self, x):
		self.val = x
		self.nxt = None
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		line = input().strip().split()
		n = int(line[0])
		x = int(line[1])
		line = input().strip().split()
		head = Node(int(line[0]))
		tail = head
		for i in range(1, n):
			tail.nxt = Node(int(line[i]))
			tail = tail.nxt
		print(countTriplets(head, x))


def countTriplets(head, x):
	l = []
	temp = head
	while temp != None:
		l.append(temp.val)
		temp = temp.nxt
	n = len(l)
	l.sort()
	count = 0
	for i in range(n - 2):
		left = i + 1
		right = n - 1
		while left < right:
			if l[i] + l[left] + l[right] == x:
				count += 1
				left += 1
				right -= 1
			elif l[i] + l[left] + l[right] > x:
				right -= 1
			else:
				left += 1
	return count

class Node:

	def __init__(self, x):
		self.val = x
		self.nxt = None
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		line = input().strip().split()
		n = int(line[0])
		x = int(line[1])
		line = input().strip().split()
		head = Node(int(line[0]))
		tail = head
		for i in range(1, n):
			tail.nxt = Node(int(line[i]))
			tail = tail.nxt
		print(countTriplets(head, x))


def countTriplets(head, x):
	l = []
	while head is not None:
		l.append(head.val)
		head = head.nxt
	c = 0
	n = len(l)
	l = l[::-1]
	for i in range(n - 1, -1, -1):
		k = i - 1
		j = 0
		while j < k:
			if l[i] + l[j] + l[k] == x:
				c += 1
				j += 1
				k -= 1
			elif l[i] + l[j] + l[k] < x:
				j += 1
			else:
				k -= 1
	return c

class Node:

	def __init__(self, x):
		self.val = x
		self.nxt = None
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		line = input().strip().split()
		n = int(line[0])
		x = int(line[1])
		line = input().strip().split()
		head = Node(int(line[0]))
		tail = head
		for i in range(1, n):
			tail.nxt = Node(int(line[i]))
			tail = tail.nxt
		print(countTriplets(head, x))


import collections

def countTriplets(head, x):
	arr = []
	dup = head
	while dup:
		arr.append(dup.val)
		dup = dup.nxt
	arr = arr[::-1]
	carr = collections.Counter(arr)
	cnt = 0
	for i in range(len(arr)):
		for j in range(i, len(arr)):
			k = x - arr[i] - arr[j]
			if arr[i] != arr[j] != k and carr[k] != 0 and (i < j < arr.index(k)):
				cnt += 1
	return cnt


def countTriplets(head, x):
	arr = []
	p = 0
	n = 0
	while head:
		arr.append(head.val)
		head = head.nxt
		n += 1
	arr.sort()
	y = []
	for i in range(0, n - 2):
		l = i + 1
		r = n - 1
		while l < r:
			if arr[i] + arr[l] + arr[r] == x:
				p += 1
				l += 1
				r -= 1
			elif arr[i] + arr[l] + arr[r] < x:
				l += 1
			else:
				r -= 1
	return p


def countTriplets(head, x):
	arr = []
	temp = head
	while temp != None:
		arr.append(temp.val)
		temp = temp.nxt
	c = 0
	arr.sort()
	for i in range(0, len(arr) - 2):
		j = i + 1
		k = len(arr) - 1
		while j < k:
			s = arr[i] + arr[j] + arr[k]
			if s == x:
				c += 1
				j += 1
				k -= 1
			elif s > x:
				k -= 1
			else:
				j += 1
	return c


from collections import deque

def countPairs(head, x):
	if head == None or head.nxt == None or x < 2:
		return 0
	dq = deque()
	walk = head
	while walk:
		dq.append(walk.val)
		walk = walk.nxt
	ret = 0
	l = dq.popleft()
	r = dq.pop()
	while 1:
		if l + r == x:
			ret += 1
		if len(dq) == 0:
			return ret
		if l + r > x:
			l = dq.popleft()
		else:
			r = dq.pop()

def countTriplets(head, x):
	ret = 0
	while head != None:
		ret += countPairs(head.nxt, x - head.val)
		head = head.nxt
	return ret


def countTriplets(head, x):

	def reverse(head):
		prev = None
		curr = head
		fut = head.nxt
		while curr:
			curr.nxt = prev
			prev = curr
			curr = fut
			if fut:
				fut = fut.nxt
		return prev

	def insert(head):
		curr = head
		ele = Node(curr.val)
		new = ele
		curr = curr.nxt
		while curr:
			new.nxt = Node(curr.val)
			new = new.nxt
			curr = curr.nxt
		return ele
	new = reverse(insert(head))
	curr = head
	count = 0
	val1 = False
	if head.val < new.val:
		val1 = True
	while curr.nxt.nxt:
		summ = res = curr.val
		temp1 = curr.nxt
		temp2 = new
		while val1 and temp1.val < temp2.val or (not val1 and temp1.val > temp2.val):
			res += temp1.val + temp2.val
			if res == x:
				count += 1
				temp1 = temp1.nxt
				temp2 = temp2.nxt
			elif res > x:
				if temp2.val > temp1.val:
					temp2 = temp2.nxt
				else:
					temp1 = temp1.nxt
			elif temp1.val > temp2.val:
				temp2 = temp2.nxt
			else:
				temp1 = temp1.nxt
			res = summ
		curr = curr.nxt
	return count


def countTriplets(head, x):
	a = head
	count = 0
	while a != None:
		p = x - a.val
		s = set()
		q = a.nxt
		while q != None:
			if p - q.val in s:
				count += 1
				q = q.nxt
			else:
				s.add(q.val)
				q = q.nxt
		a = a.nxt
	return count


def countTriplets(head, x):
	l = []
	while head != None:
		l.append(head.val)
		head = head.nxt
	n = len(l)
	if n <= 2:
		return 0
	if l[0] > l[-1]:
		l = l[::-1]
	i = 0
	ans = 0
	while i < n - 2:
		req = x - l[i]
		j = i + 1
		k = n - 1
		while j < k:
			if l[j] + l[k] == req:
				ans += 1
				curr = l[j]
				while j < k and l[j] == curr:
					j += 1
				curr = l[k]
				while j < k and l[k] == curr:
					k -= 1
			elif l[j] + l[k] < req:
				curr = l[j]
				while j < k and l[j] == curr:
					j += 1
			else:
				curr = l[k]
				while j < k and l[k] == curr:
					k -= 1
		curr = l[i]
		while i < n - 2 and l[i] == curr:
			i += 1
	return ans


def countTriplets(head, x):
	l = []
	res = 0
	if not head:
		return 0
	while head:
		l.append(head.val)
		head = head.nxt
	l.sort()
	for i in range(len(l) - 2):
		left = i + 1
		right = len(l) - 1
		while left < right:
			k = l[i] + l[right] + l[left]
			if k == x:
				res += 1
				left += 1
				right -= 1
			elif k > x:
				right -= 1
			else:
				left += 1
	return res