Read problems statements in Mandarin, Russian and Vietnamese as well. 

There are N sets of integers from 1 to K both inclusive. Find out number of pairs of sets whose union contains all the K elements.

------ Input ------ 

The first line contains an integer T denotes number of test cases.
The first line of each test case contains two space separated integers N, K.
The each of the next line first contains an integer len_{i} denoting number of elements in the i-th set, followed by len_{i} space separated integers in the range [1, K] denoting the elements in the set.

------ Output ------ 

For each test case, output a single integer corresponding to the answer.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ N, K ≤ 2500$
$1 ≤ len_{i} ≤ K$
$Note that a set can't contain repeated elements.$
$1 ≤ len_{1} + len_{2} + .. + len_{N} ≤ 10000$

------ Subtasks ------ 

Subtask #1 (40 points)

$1 ≤ T ≤ 10$
$1 ≤ N, K ≤ 250$
$1 ≤ len_{1} + len_{2} + .. + len_{N} ≤ 1000$

Subtask #2 (60 points)

$original constraints.$

----- Sample Input 1 ------ 
3
2 2
1 1
1 1
3 2
2 1 2
2 1 2
2 1 2
3 4
3 1 2 3
4 1 2 3 4
3 2 3 4
----- Sample Output 1 ------ 
0
3
3
----- explanation 1 ------ 
Example 1. No pair of sets is there with its union = 2.
For example 2 and 3, all the pairs are valid.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
t = int(input())
for t_ in range(t):
	(n, k) = list(map(int, input().split()))
	d = {}
	for _ in range(n):
		arr = frozenset(map(int, input().split()[1:]))
		if arr not in d:
			d[arr] = 0
		d[arr] += 1
	ans = 0
	for s1 in d.keys():
		if len(s1) == k:
			ans += d[s1] * (d[s1] - 1)
		for s2 in d.keys():
			if s1 != s2 and len(s1 | s2) == k:
				ans += d[s1] * d[s2]
	print(ans // 2)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	sets = {}
	ans = 0
	for i in range(n):
		arr = input().split()
		arr.remove(arr[0])
		arr = frozenset(arr)
		if arr in sets.keys():
			sets[arr] += 1
		else:
			sets[arr] = 1
	for i in sets.keys():
		if len(i) == k:
			ans += sets[i] * (sets[i] - 1)
	for i in sets.keys():
		for j in sets.keys():
			if i != j and len(i.union(j)) == k:
				ans += sets[i] * sets[j]
	print(int(ans / 2))


for _ in range(int(input())):
	(n, k) = map(int, input().strip().split())
	list1 = list()
	dummy = set([i for i in range(1, k + 1)])
	for i in range(n):
		list1.append(list(map(int, input().strip().split())))
		list1[i] = set(list1[i][1:])
	count = 0
	ext = []
	for i in list1:
		a = dummy - i
		ext.append(a)
	for (i, s) in enumerate(ext):
		for s1 in list1[i + 1:]:
			if s.issubset(s1):
				count += 1
	print(count)


for _ in range(int(input())):
	l = []
	(n, k) = map(int, input().split())
	z = set([i for i in range(1, k + 1)])
	for i in range(n):
		s = [int(i) for i in input().split()]
		s = set(s[1:])
		l.append(s)
	extra = []
	for i in l:
		req = z - i
		extra.append(req)
	cnt = 0
	for (i, s) in enumerate(extra):
		for s1 in l[i + 1:]:
			if s.issubset(s1):
				cnt += 1
	print(cnt)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	sets = []
	for j in range(N):
		l = [int(x) for x in input().split()]
		sets.append(set(l[1:]))
	target = set((x for x in range(1, K + 1)))
	setcomp = []
	count = 0
	for k in sets:
		rem = target - k
		setcomp.append(rem)
	for (a, setcomps) in enumerate(setcomp):
		for set1 in sets[a + 1:]:
			if setcomps.issubset(set1):
				count += 1
	print(count)


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	sets = {}
	ans = 0
	for c in range(n):
		inp = list(map(int, input().split()))
		del inp[0]
		inp = frozenset(inp)
		if inp in sets.keys():
			sets[inp] += 1
		else:
			sets[inp] = 1
	for z in sets.keys():
		if len(z) == k:
			ans += sets[z] * (sets[z] - 1)
	for a in sets.keys():
		for b in sets.keys():
			if a != b and len(a.union(b)) == k:
				ans += sets[a] * sets[b]
	print(ans // 2)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	(arr, ans) = (dict(), 0)
	for _ in range(n):
		s = [int(i) for i in input().split()]
		s.pop(0)
		s = frozenset(s)
		if s in arr:
			arr[s] += 1
		else:
			arr[s] = 1
	for keys in arr:
		if len(keys) == k:
			ans += arr[keys] * (arr[keys] - 1)
	for a in arr:
		for b in arr:
			if a != b and len(a.union(b)) == k:
				ans += arr[a] * arr[b]
	print(ans // 2)


def method_hard():
	A = [None] * n
	cnt = [0] * (k + 1)
	for i in range(n):
		A[i] = list(map(int, input().split()[1:]))
		for j in A[i]:
			cnt[j] += 1
	minIdx = 1
	minValue = cnt[1]
	for i in range(2, k + 1):
		if minValue > cnt[i]:
			minValue = cnt[i]
			minIdx = i
	cmp = lambda x: (cnt[x], x)
	for i in range(n):
		A[i].sort(key=cmp)
	tmp = [i for i in range(1, k + 1)]
	tmp.sort(key=cmp)
	containMinIdx = {}
	ans = 0
	for i in range(n):
		containMinIdx[i] = minIdx in A[i]
		if not containMinIdx[i]:
			continue
		idx = 0
		f = []
		for v in tmp:
			if idx == len(A[i]) or A[i][idx] != v:
				f.append(v)
			else:
				idx += 1
		for j in range(n):
			if j <= i and containMinIdx[j]:
				continue
			lenf = len(f)
			idxf = 0
			for z in A[j]:
				if idxf == lenf:
					break
				if cnt[z] <= cnt[f[idxf]]:
					if z == f[idxf]:
						idxf += 1
				else:
					break
			if idxf == lenf:
				ans += 1
	print(ans)

def method_easy():
	A = []
	for i in range(n):
		tmp = list(map(int, input().split()))
		tmp.pop(0)
		mask = 0
		for v in tmp:
			mask |= 1 << v - 1
		A.append(mask)
	ans = 0
	for i in range(n):
		for j in range(i + 1, n):
			if A[i] | A[j] == (1 << k) - 1:
				ans += 1
	print(ans)

def solve():
	global n, k
	(n, k) = map(int, input().split())
	if k > 0:
		method_hard()
	else:
		method_easy()
T = int(input())
while T > 0:
	solve()
	T -= 1


t = int(input())
for t0 in range(t):
	s = [int(i) for i in input().strip().split()]
	(n, k) = (s[0], s[1])
	st = []
	ts1 = []
	ts2 = []
	for i in range(n):
		s = [int(i) for i in input().strip().split()]
		m = s[0]
		del s[0]
		st.append(set(s))
	tot = 0
	cts = [0 for i in range(k + 1)]
	cts[0] = n + 1
	for i in range(n):
		for j in st[i]:
			cts[j] += 1
	mn = min(cts)
	ind = cts.index(mn)
	l1 = 0
	l2 = 0
	fl = set([i for i in range(1, k + 1)])
	for i in range(n):
		if ind in st[i]:
			ts1.append(fl - st[i])
			l1 += 1
		else:
			l2 += 1
			ts2.append(st[i])
	for i in range(l1):
		for j in range(i + 1, l1):
			fl = 0
			for p in ts1[i]:
				if p in ts1[j]:
					fl = 1
					break
			if fl == 0:
				tot += 1
		for j in range(l2):
			fl = 0
			for p in ts1[i]:
				if p not in ts2[j]:
					fl = 1
					break
			if fl == 0:
				tot += 1
	print(tot)


import copy

def main(args):
	t = int(input())
	while t > 0:
		(n, k) = input().split()
		(n, k) = (int(n), int(k))
		wholeset = set((i for i in range(1, k + 1)))
		a = [[] for i in range(n)]
		for i in range(n):
			input_stream = input().split()
			a[i] = set(map(int, input_stream[1:]))
		c = 0
		for i in range(n):
			diffset = wholeset - a[i]
			for j in range(i + 1, n):
				if find_set(diffset, a[j]):
					c += 1
		print(c)
		t -= 1

def find_set(set1, set2):
	for i in set1:
		if i not in set2:
			return False
	return True
import sys
sys.exit(main(sys.argv))


num_tests = int(input())
for _ in range(num_tests):
	(n, k) = map(int, input().split())
	num_lists = []
	for _ in range(n):
		num_lists.append([int(i) for i in input().split()])
	containing = [set([]) for _ in range(k + 1)]
	total = 0
	num_lists.sort(key=len)
	for i in range(n):
		nums = num_lists[i]
		if len(nums) >= k // 2:
			num_set = set(nums[1:])
			possible_complements = None
			for j in range(1, k + 1):
				if j not in num_set:
					if possible_complements is None:
						possible_complements = set(containing[j])
					else:
						possible_complements &= containing[j]
			total += i if possible_complements is None else len(possible_complements)
		for num in nums[1:]:
			containing[num].add(i)
	print(total)


class Node:

	def __init__(self, arr):
		self.set = set(arr[1:])
		self.size = arr[0]
		self.counter = 1
cases = int(input())
for i in range(cases):
	(n, k) = [int(n) for n in input().split(' ')]
	total_sets = 0
	lists = []
	dict = {}
	for j in range(n):
		row = [int(n) for n in input().split(' ')]
		new_node = Node(row)
		if str(new_node.set) not in dict:
			dict.update({str(new_node.set): new_node})
		else:
			dict[str(new_node.set)].counter += 1
	lists = sorted(list(dict.values()), key=lambda node: node.size, reverse=True)
	new_n = len(lists)
	for outer in range(new_n):
		if lists[outer].size == k:
			total_sets += lists[outer].counter * n - lists[outer].counter * (lists[outer].counter + 1) / 2
			continue
		if lists[outer].size < k / 2:
			break
		for inner in range(outer + 1, new_n):
			if k - lists[outer].size > lists[inner].size:
				break
			elif len(lists[outer].set.union(lists[inner].set)) == k:
				total_sets += lists[inner].counter * lists[outer].counter
	print(int(total_sets))


def binomial(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return int(ntok / ktok)
	else:
		return 0
t = int(input())
for z in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	a = []
	ret = 0
	d = dict()
	bla = 0
	for i in range(n):
		a.append([int(x) for x in input().split()])
		if len(a[i]) == k + 1:
			ret = ret + n - 1 - bla
			bla += 1
			a[i] = []
		else:
			for ai in a[i][1:]:
				if ai in d:
					d[ai].add(i)
				else:
					d[ai] = set()
					d[ai].add(i)
	if bla == n:
		print(binomial(n, 2))
		continue
	if len(d) != k and bla == 0:
		print(0)
		continue
	hlp = set()
	d1 = sorted(d, key=lambda k: len(d[k]))
	for t in d[d1[0]]:
		st = set(list(range(1, k + 1))) - set(a[t][1:])
		tmp = 1
		flag = 0
		while flag == 0 and tmp < len(d1):
			if d1[tmp] in st:
				flag = 1
			else:
				tmp += 1
		if flag == 0:
			continue
		for y in d[d1[tmp]]:
			if t != y and st <= set(a[y][1:]) and ((t, y) not in hlp):
				ret = ret + 1
				if d1[0] in set(a[y][1:]):
					hlp.add((t, y))
					hlp.add((y, t))
	print(ret)


for t in range(int(input())):
	(n, k) = [int(x) for x in input().strip().split()]
	valid = [set() for ki in range(k)]
	mysets = sorted(([int(x) - 1 for x in input().strip().split()] for myset in range(n)))
	can_match_len = k // 2 - 1
	ans = 0
	for (mysetsi, myset) in enumerate(mysets):
		if myset[0] < can_match_len:
			for si in myset[1:]:
				valid[si].add(mysetsi)
		else:
			matches = None
			myset = sorted(myset[1:])
			myseti = 0
			for i in range(k):
				if myseti < len(myset) and i == myset[myseti]:
					myseti += 1
					valid[i].add(mysetsi)
				elif matches is not None:
					matches = valid[i].intersection(matches)
				else:
					matches = valid[i]
			ans += len(matches) if matches is not None else mysetsi
	print(ans)


def search_value(l, v, start_index):
	end_index = len(l)
	index = start_index
	while index < end_index and l[index] < v:
		index += 1
	if index < end_index and l[index] == v:
		return (1, index)
	return (0, index)

def check_completion(list1, list2, K):
	index1 = 0
	index2 = 0
	for i in range(1, K + 1):
		(found, index1) = search_value(list1, i, index1)
		if not found:
			(found, index2) = search_value(list2, i, index2)
		if not found:
			return 0
	return 1

def solve(bit_sets, expected_result):
	result = 0
	N = len(bit_sets)
	for i in range(N):
		s = bit_sets[i]
		for j in range(i + 1, N):
			if s | bit_sets[j] == expected_result:
				result += 1
	return result

def make_bit_set(l, init_value):
	s = init_value
	for i in l:
		s |= 1 << i
	return s
T = int(input())
for t in range(T):
	(N, K) = [int(x) for x in input().split()]
	bit_sets = []
	init_value = 1 << K + 1
	expected_result = (init_value << 1) - 1 - 1
	for n in range(N):
		line = [int(x) for x in input().split()]
		s = make_bit_set(line[1:], init_value)
		bit_sets.append(s)
	print(solve(bit_sets, expected_result))


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	a = []
	b = []
	c = 0
	yu = 0
	for j in range(n):
		e = list(map(int, input().split()))
		l = e[0]
		e = e[1:]
		if l == k:
			a.append(set(e))
		elif len(b) > 0:
			r = set(e)
			if d == r and yu > 0:
				c += yu
				b.append(r)
			else:
				yu = 0
				for nj in b:
					if len(nj.union(r)) == k:
						c += 1
						yu += 1
				b.append(r)
				d = r
		else:
			d = set(e)
			b.append(d)
	if len(a) >= 1:
		c = c + ((n - 1) * len(a) - len(a) * (len(a) - 1) // 2)
	print(c)


import bisect
T = int(input())
for _ in range(T):
	(N, K) = list(map(int, input().strip().split(' ')))
	if K > 1000 or (N <= 250 and K <= 250):
		Set = []
		length = []
		for i in range(N):
			A = list(map(int, input().strip().split(' ')))
			length += [A[0]]
			A = A[1:]
			x = 0
			for i in range(len(A)):
				x += 2 ** (A[i] - 1)
			Set += [[len(A), x]]
		Set = sorted(Set)
		length = sorted(length)
		ans = 0
		tar = 2 ** K - 1
		for i in range(len(Set)):
			(L, x) = Set[i]
			temp = K - L
			position = bisect.bisect_left(length, temp)
			if position >= len(length):
				continue
			for j in range(position, len(length)):
				if j != i:
					y = Set[j][1]
					if x | y == tar:
						ans += 1
		print(ans // 2)
	else:
		Set = [[0 for j in range(K)] for i in range(N)]
		big = []
		ans = 0
		tar = 2 ** K - 1
		for i in range(N):
			A = list(map(int, input().strip().split(' ')))
			A = A[1:]
			temp = 0
			for x in A:
				Set[i][x - 1] = 1
				temp += 2 ** (x - 1)
			big += [temp]
		Containone = [set() for i in range(K)]
		for j in range(K):
			for i in range(N):
				if Set[i][j] == 1:
					Containone[j].add(i)
		GGG = [[] for i in range(N)]
		for i in range(N):
			for j in range(K):
				if Set[i][j] == 0:
					GGG[i] += [j]
		for x in range(N):
			if big[x] == tar:
				ans += N - 1
				continue
			MIN = N + 1
			check = 0
			for y in GGG[x]:
				if len(Containone[y]) < MIN:
					check = y
					MIN = len(Containone[y])
			for L in Containone[check]:
				if big[L] | big[x] == tar:
					ans += 1
		print(ans // 2)


import time

def unionlength(a, b, k):
	if len(b) < len(a):
		x = b
		y = a
	else:
		x = a
		y = b
	count = len(a) + len(b)
	for val in x:
		if val in y:
			count -= 1
		if count < k:
			return k - 1
	return count
start = time.time()
t = int(input())
for u in range(t):
	inp = input().split()
	n = int(inp[0])
	k = int(inp[1])
	l = []
	D = {}
	c2 = 0
	for i in range(n):
		inp = input().split()
		x = set()
		for val in range(1, len(inp)):
			x.add(int(inp[val]))
		if len(x) == k:
			c2 += 1
		else:
			l.append([len(x), x])
		for val in inp[1:]:
			val = int(val)
			try:
				D[val].add(i)
			except:
				D[val] = set()
				D[val].add(i)
	count = 0
	try:
		for sets in l:
			if time.time() - start > 4:
				print(1 / 0)
			flag = 0
			s = set()
			for i in range(1, k + 1):
				if i in sets[1]:
					continue
				elif flag == 0:
					s = set(D[i])
					flag = 1
				else:
					s = s & D[i]
			count += len(s)
		print((count + c2 * (n - c2) + c2 * (c2 - 1)) // 2)
	except KeyError:
		print(0)
	except ZeroDivisionError:
		l.sort()
		count = 0
		for i in range(n - c2 - 1):
			for j in range(n - c2 - 1, i, -1):
				if l[j][0] + l[i][0] < k:
					break
				if unionlength(l[i][1], l[j][1], k) == k:
					count += 1
		print(count + c2 * (n - c2) + c2 * (c2 - 1) // 2)


def main():
	T = int(input())
	for i in range(T):
		(N, K) = input().split(' ')
		(N, K) = (int(N), int(K))
		sets = []
		for i in range(N):
			arr = input().split(' ')
			arr = [int(n) for n in arr]
			del arr[0]
			sets.append(arr)
		sets = sorted(sets, key=lambda x: len(x), reverse=True)
		solve(K, sets)

def solve(K, sets):
	(new, cover) = setsToBin(K, sets)
	biggest = (1 << K) - 1
	if cover < biggest:
		print(0)
		return
	count = 0
	for i in range(len(new)):
		if new[i] == biggest:
			count += len(new) - 1 - i
			continue
		if i < len(new) - 1:
			if len(sets[i]) + len(sets[i + 1]) < K:
				break
		for j in range(i + 1, len(new)):
			if len(sets[i]) + len(sets[j]) < K:
				break
			if new[i] | new[j] == biggest:
				count += 1
	print(count)

def setsToBin(K, sets):
	new = []
	cover = 0
	for s in sets:
		num = 0
		for i in s:
			num |= 1 << i - 1
		new.append(num)
		cover |= num
	return (new, cover)
main()


T = int(input())
for t in range(T):
	s = input().split()
	n = int(s[0])
	k = int(s[1])
	l = [set()] * n
	for i in range(n):
		temp_list = [int(r) for r in input().split()[1:]]
		l[i] = set(temp_list)
	pair_count = 0
	ideal = set(range(1, k + 1))
	for i in range(len(l)):
		diff = ideal.difference(l[i])
		for j in range(i + 1, len(l)):
			if diff.issubset(l[j]):
				pair_count += 1
	print(pair_count)