Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Shlok and Sachin are good friends. Shlok wanted to test Sachin, so he wrote down a string $S$ with length $N$ and one character $X$. He wants Sachin to find the number of different substrings of $S$ which contain the character $X$ at least once. Sachin is busy with his girlfriend, so he needs you to find the answer.

Two substrings of $S$ are considered different if their positions in $S$ are different.

------  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 a single integer $N$. 
The second line contains a string $S$ with length $N$, followed by a space and a character $X$.

------  Output ------
For each test case, print a single line containing one integer — the number of substrings of $S$ that contain $X$.

------  Constraints ------
$1 ≤ T ≤ 1,000$
$1 ≤ N ≤ 10^{6}$
$S$ contains only lowercase English letters
$X$ is a lowercase English letter
the sum of $N$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (30 points): the sum of $N$ over all test cases does not exceed $10^{3}$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
2
3
abb b
6
abcabc c
----- Sample Output 1 ------ 
5
15
----- explanation 1 ------ 
Example case 1: The string "abb" has six substrings: "a", "b", "b", "ab", "bb", "abb". The substrings that contain 'b' are "b", "b", "ab", "bb", "abb".

Source: codechef | Difficulty: MEDIUM
Tags: Combinatorics


Solutions:
(k, k2) = (12, 13)
for i in range(int(input())):
	str = int(input())
	(str1, var) = input().split()
	(sum, s) = (0, 0)
	for l in range(str):
		if str1[l] == var:
			s = l + 1
		sum += s
	print(sum)


tc = int(input())
for i in range(tc):
	N = int(input())
	(S, X) = input().split()
	res = 0
	t = 0
	for ltr in range(len(S)):
		if S[ltr] == X:
			t = ltr + 1
		res += t
	print(res)


for i in range(int(input())):
	n = int(input())
	(str1, var) = input().split()
	(ans, k) = (0, 0)
	for j in range(n):
		if str1[j] == var:
			k = j + 1
		ans += k
	print(ans)


for _ in range(int(input())):
	n = int(input())
	(s, x) = input().split()
	(answer, cnt) = (0, 0)
	for i in range(n):
		if s[i] == x:
			answer = answer + (cnt + 1) * (n - i)
			cnt = 0
		else:
			cnt += 1
	print(answer)


for _ in range(int(input())):
	n = int(input())
	(s, x) = input().split()
	c = 0
	ind = [-1]
	for i in range(n):
		if s[i] == x:
			ind.append(i)
	for i in range(1, len(ind)):
		st = ind[i] - ind[i - 1]
		f = n - ind[i]
		c += st * f
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	(s, x) = input().split()
	nox = 0
	count = 0
	for i in range(n):
		if s[i] == x:
			nox += count * (count + 1) // 2
			count = 0
		else:
			count += 1
	nox += count * (count + 1) // 2
	ans = n * (n + 1) // 2 - nox
	print(ans)


for _ in range(int(input())):
	n = int(input())
	(s, x) = input().split()
	l = [-1]
	not_sub = 0
	for i in range(len(s)):
		if s[i] == x:
			l.append(i)
	l.append(n)
	for i in range(1, len(l)):
		k = l[i] - l[i - 1] - 1
		not_sub += k * (k + 1) / 2
	ans = n * (n + 1) / 2 - not_sub
	print(int(ans))


t = int(input())
for _ in range(0, t):
	n = int(input())
	(s, x) = input().split()
	(k, sm) = (0, 0)
	for i in range(1, n + 1):
		if s[-i] == x:
			k = i
		sm = sm + k
	print(sm)


def solve(n, s, x):
	ans = n * (n + 1) // 2
	a = 0
	for i in range(n):
		if s[i] != x:
			a += 1
			ans -= a
		elif s[i] == x:
			a = 0
	return ans
for _ in range(int(input())):
	n = int(input())
	(s, x) = input().split()
	print(solve(n, s, x))


t = int(input())
for _ in range(t):
	n = int(input())
	(s, x) = input().split()
	ans = n * (n + 1) // 2
	a = 0
	for i in range(n):
		if s[i] != x:
			a = a + 1
			ans = ans - a
		elif s[i] == x:
			a = 0
	print(ans)


k = int(input())
for i in range(k):
	n = int(input())
	(s, x) = input().split()
	ans = n * (n + 1) // 2
	a1 = 0
	for xx in range(n):
		if s[xx] == x:
			ans -= a1 * (a1 + 1) // 2
			a1 = 0
		elif xx + 1 == n:
			a1 += 1
			ans -= a1 * (a1 + 1) // 2
		else:
			a1 += 1
	print(ans)


tests = int(input())
for i in range(tests):
	length = int(input())
	(string, x) = input().split()
	ans = 0
	last_b_pos = -1
	for j in range(length):
		if string[j] == x:
			ans += (j - last_b_pos) * (length - j)
			last_b_pos = j
	print(ans)


case = int(input())
for i in range(case):
	n = int(input())
	(string, x) = input().split(' ')
	arr = []
	for i in range(n):
		if string[i] == x:
			arr.append(i)
	length = n
	res = 0
	while len(arr) > 0:
		last = arr.pop()
		ans = length - last
		res += (last + 1) * ans
		length = last
	print(res)


for _ in range(int(input())):
	n = int(input())
	(s, x) = input().split()
	lis = [count for (count, i) in enumerate(s) if i == x]
	tot = 0
	i = 0
	while i < n and lis != []:
		if i <= lis[0]:
			tot += n - lis[0]
			i += 1
		elif lis != []:
			lis.pop(0)
	print(tot)


for _ in range(int(input())):
	n = int(input())
	(arr, x) = map(str, input().split())
	l = []
	count = 0
	ans = 0
	for i in range(n):
		if arr[i] == x:
			l.append(i)
			count += 1
			if count >= 2:
				ans += (l[count - 2] + 1) * (l[count - 1] - l[count - 2] - 1) + l[count - 2] + 1
	if l != []:
		ans += (l[-1] + 1) * (n - 1 - l[-1]) + l[-1] + 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	(a, b) = input().split()
	(c, res) = (0, 0)
	for i in range(n):
		if a[i] == b:
			c = i + 1
		res += c
	print(res)


t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input().split(' ')
	(s, char) = (s[0], s[1])
	nextchar = {}
	i = n - 1
	pos = n
	ans = 0
	while i > -1:
		if s[i] == char:
			nextchar[i] = i
			pos = i
		else:
			nextchar[i] = pos
		i -= 1
		ans += n - i - (pos - i)
	print(ans)


for i in range(int(input())):
	n = int(input())
	(s, c) = map(str, input().split())
	subsets = n * (n + 1) // 2
	diff = 0
	t = 0
	for i in range(0, n):
		if s[i] == c:
			diff = diff + (t + 1) * t // 2
			t = 0
		else:
			t += 1
	diff += t * (t + 1) // 2
	print(subsets - diff)


for _ in range(int(input())):
	n = int(input())
	(s, x) = input().split()
	(ans, prev) = (0, -1)
	for i in range(n):
		if s[i] == x:
			ans += (i - prev) * (n - i)
			prev = i
	print(ans)


for i in range(int(input())):
	N = int(input())
	(a, b) = input().split()
	(c, res) = (0, 0)
	for i in range(len(a)):
		if a[i] == b:
			c = i + 1
		res += c
	print(res)


test_case = int(input())
while test_case:
	n = int(input())
	(s, c) = input().split()
	count = 0
	for i in range(0, n):
		for j in range(i, n):
			if s[j] == c:
				count += n - j
				break
	print(count)
	test_case = test_case - 1


for _ in range(int(input())):
	n = int(input())
	(s, k) = input().split()
	sum = 0
	prev = 0
	for i in range(n):
		if s[i] == k:
			sum += (i - prev + 1) * (n - 1 - i + 1)
			prev = i + 1
	print(sum)


t = int(input())
for _ in range(t):
	n = int(input())
	(str, x) = input().split()
	(result, characterCount) = (0, 0)
	for i in range(n):
		if str[i] == x:
			result += (characterCount + 1) * (n - i)
			characterCount = 0
		else:
			characterCount += 1
	print(result)


for _ in range(int(input())):
	n = int(input())
	(s, k) = map(str, input().split())
	arr = [0]
	for i in range(n):
		if s[i] == k:
			arr.append(i + 1)
	if len(arr) == 1:
		print(0)
	else:
		s = 0
		for i in range(1, len(arr)):
			s = s + (n - arr[i] + 1) * (arr[i] - arr[i - 1])
		print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	(s, char) = map(str, input().split())
	ans = 0
	prev = 0
	for i in range(n):
		if s[i] == char:
			ans += (i - prev + 1) * (n - 1 - i + 1)
			prev = i + 1
	print(ans)


def sumS(s):
	return s * (s + 1) // 2
for _ in range(int(input())):
	l = int(input())
	(string, char) = input().split()
	total = sumS(l)
	notc = sum((sumS(len(i)) for i in string.split(char)))
	print(total - notc)


for _ in range(int(input())):
	n = int(input())
	(s, x) = list(map(str, input().split()))
	a = n * (n + 1) / 2
	c = 0
	for i in range(n):
		if s[i] == x:
			a -= c * (c + 1) / 2
			c = 0
		else:
			c += 1
	else:
		a -= c * (c + 1) / 2
	print(int(a))


t = int(input())
while t != 0:
	n = int(input())
	(s, x) = input().split()
	k2 = -1
	count = 0
	for k in range(n):
		if s[k] == x:
			count += (n - k) * (k - k2)
			k2 = k
	print(count)
	t -= 1


t = int(input())
for k in range(t):
	n = int(input())
	(s, c) = map(str, input().strip().split())
	res = 0
	k = 0
	for i in range(n):
		if s[i] == c:
			res = res + (n - i) * (i + 1 - k)
			k = i + 1
	print(res)


for _ in range(int(input())):
	n = int(input())
	(s, x) = map(str, input().split())
	total = n * (n + 1) // 2
	l = []
	for i in range(n):
		if s[i] == x:
			l.append(i + 1)
	if len(l) == 0:
		print(0)
		continue
	ans = (l[0] - 1) * l[0] // 2
	for i in range(len(l) - 1):
		t = l[i + 1] - l[i] - 1
		if t > 0:
			ans += t * (t + 1) // 2
	if l[-1] != n:
		t = n - l[-1]
		ans += t * (t + 1) // 2
	print(total - ans)


try:
	for t in range(int(input())):
		n = int(input())
		s = input()
		x = s[-1]
		c = 0
		for j in range(0, n):
			for k in range(j + 1, n + 1):
				if x in s[j:k]:
					c = c + 1 + (n - k)
					break
		print(c)
except EOFError as e:
	pass


t = int(input())
while t:
	n = int(input())
	(s, x) = map(str, input().split())
	c = 0
	l = 0
	while x in s:
		ind = s.index(x)
		c += (n - ind) * (ind - l + 1)
		l = ind + 1
		s = s.replace(x, '1', 1)
	print(c)
	t -= 1


def sumN(t):
	return t * (t + 1) // 2
for _ in range(int(input())):
	n = int(input())
	(s, c) = input().split()
	m = sum((sumN(len(i)) for i in s.split(c)))
	print(sumN(n) - m)


for _ in range(int(input())):
	n = int(input())
	summ = n * (n + 1)
	summ = summ // 2
	(s, target) = input().split()
	count = 0
	a = 0
	summ1 = 0
	for i in range(n):
		if s[i] == target:
			summ1 = count * (count + 1)
			summ1 = summ1 // 2
			a += summ1
			count = 0
			summ1 = 0
		else:
			count += 1
	summ1 = 0
	if count != 0:
		summ1 = count * (count + 1)
		a += summ1 // 2
	print(summ - a)


T = int(input())
for i in range(T):
	n = int(input())
	(a, b) = map(str, input().split())
	l = []
	i = 0
	co = 0
	while i < n:
		e = a[i]
		if e == b:
			l.append(co)
			co = 0
		else:
			co = co + 1
		i = i + 1
	l.append(co)
	ans = 0
	for e in l:
		ans = ans + e * (e + 1) // 2
	z = n * (n + 1) // 2
	print(z - ans)


t = int(input())
for _ in range(t):
	n = int(input())
	(s, x) = map(str, input().split())
	h = s.split(x)
	ans = n * (n + 1) // 2
	c = 0
	for i in h:
		if i != '':
			c += len(i) * (len(i) + 1) // 2
	print(ans - c)


for a in range(int(input())):
	b = 0
	c = int(input())
	(d, e) = input().split()
	f = [-1]
	for g in range(c):
		if d[g] == e:
			f.append(g)
	for g in range(1, len(f)):
		b += (f[g] - f[g - 1]) * (c - f[g])
	print(b)


t = int(input())
for _ in range(t):
	n = int(input())
	(s, x) = input().split()
	count = 0
	k = [-1]
	for i in range(n):
		if s[i] == x:
			count += 1
			k.append(i)
	ans = 0
	for i in range(1, count + 1):
		ans += (n - k[i]) * (k[i] - k[i - 1])
	print(ans)


def substringCount(n, string, char):
	last = -1
	count = 0
	for i in range(len(string)):
		if string[i] == char:
			last = i
		count += last + 1
	return count
noOfTests = int(input())
for tests in range(noOfTests):
	strlen = int(input())
	(string, char) = input().split()
	print(substringCount(strlen, string, char))


def func(s, y):
	m = 0
	k = 0
	r = 0
	for j in s:
		if j != y:
			m += 1
		else:
			k = k + m * (m + 1) // 2
			m = 0
	k = k + m * (m + 1) // 2
	r = r + n * (n + 1) // 2 - k
	return r
t = int(input())
lis = []
for i in range(t):
	n = int(input())
	(s, y) = input().split()
	print(func(s, y))


t = int(input())
sum = 0
if sum < 1000:
	while t > 0:
		n = int(input())
		sum += n
		count = 0
		s = input()
		st = s.split()[0]
		x = s.split()[1]
		l = -1
		for i in range(len(st)):
			if st[i] == x:
				l = i
			count += l + 1
		t -= 1
		print(count)


def countSubstrings(string, len, x):
	res = 0
	count = 0
	for i in range(len):
		if string[i] == x:
			res += (count + 1) * (len - i)
			count = 0
		else:
			count += 1
	return res
testCases = int(input())
while testCases > 0:
	n = int(input())
	inp = input().split(' ')
	print(countSubstrings(inp[0], n, inp[1]))
	testCases = testCases - 1


def solution(n, string, letter):
	totalsub = Nnumber(n)
	missub = sum((Nnumber(len(j)) for j in string.split(letter)))
	return totalsub - missub

def Nnumber(n):
	return n * (n + 1) // 2
test = int(input())
for i in range(test):
	n = int(input())
	(string, letter) = input().split()
	k = solution(n, string, letter)
	print(k)


def countsub(S, N, X):
	res = 0
	count = 0
	for i in range(N):
		if S[i] == X:
			res += (count + 1) * (N - i)
			count = 0
		else:
			count += 1
	return res
T = int(input())
while T:
	N = int(input())
	s = input()
	l = s.split()
	S = l[0]
	X = l[1]
	print(countsub(S, N, X))
	T = T - 1


gets = lambda n: n * (n + 1) // 2

def res(num, x, y):
	return gets(num) - sum((gets(len(i)) for i in x.split(y)))
for i in range(int(input())):
	num = int(input())
	(x, y) = input().split()
	print(res(num, x, y))


for i in range(int(input())):
	n = int(input())
	(s, s1) = input().split()
	c = 0
	k = 0
	for j in range(n):
		for j1 in range(j, n):
			if s[j1] == s1:
				c = c + (n - j1)
				break
	print(c)


def solver(sn, x):
	c = 0
	sol = 0
	sol1 = 0
	for i in sn:
		if i != x:
			c += 1
		else:
			sol += c * (c + 1) // 2
			c = 0
	sol += c * (c + 1) // 2
	sol1 += ns * (ns + 1) // 2 - sol
	return sol1
t = int(input())
for i in range(t):
	ns = int(input())
	(sn, x) = map(str, input().split())
	print(solver(sn, x))


t = int(input())
for _ in range(t):
	n = int(input())
	(s, x) = list(input().split())
	count = 0
	res = 0
	for i in range(n):
		if s[i] == x:
			res = res + (count + 1) * (n - i)
			count = 0
		else:
			count = count + 1
	print(res)


for _ in range(int(input())):
	n = int(input())
	(s, k) = map(str, input().split())
	l = [0, 0]
	count = 0
	for i in s:
		if i == k:
			l[1] = max(l) + 1
			count += l[1]
		else:
			l[0] = max(l) + 1
			count += l[1]
	print(count)


for _ in range(int(input())):
	Lstr = int(input())
	(str_in, char) = input().split()
	res = 0
	count = 0
	n = len(str_in)
	for i in range(n):
		if str_in[i] == char:
			res += (count + 1) * (n - i)
			count = 0
		else:
			count += 1
	print(res)


try:
	for i in range(int(input())):
		a = int(input())
		(n, m) = input().split()
		x = a * (a + 1) // 2
		l = n.split(m)
		for i in l:
			red = len(i) * (len(i) + 1) // 2
			x -= red
		print(x)
except:
	pass


def nextOccurrence(strr, n, start, ch):
	for i in range(start, n):
		if strr[i] == ch:
			return i
	return -1

def countSubStr(strr, n, ch):
	cnt = 0
	j = nextOccurrence(strr, n, 0, ch)
	for i in range(n):
		while j != -1 and j < i:
			j = nextOccurrence(strr, n, j + 1, ch)
		if j == -1:
			break
		cnt += n - j
	return cnt
t = int(input())
while t:
	n = int(input())
	(s1, s2) = map(str, input().split())
	print(countSubStr(s1, n, s2))
	t = t - 1


try:
	for _ in range(int(input())):
		l = int(input())
		(string, x) = input().split()
		sum1 = (l + 1) * l // 2
		new = list(string.split(x))
		mynew = sum([(len(i) + 1) * len(i) // 2 for i in new])
		print(sum1 - mynew)
except EOFError:
	pass


t = int(input())
for _ in range(t):
	l = int(input())
	(string, x) = input().split()
	i = 0
	sum = 0
	for i in range(l):
		for j in range(i, l):
			if string[j] == x:
				sum = sum + (l - i) - (j - i)
				break
	print(sum)


t = int(input())
for u in range(t):
	l = int(input())
	(string, x) = input().split()
	sum1 = (l + 1) * l // 2
	new = list(string.split(x))
	mynew = sum([(len(i) + 1) * len(i) // 2 for i in new])
	print(sum1 - mynew)


t = int(input())
while t > 0:
	n = int(input())
	(str, x) = input().split()
	(c, ans) = (0, 0)
	for i in range(n):
		if str[i] == x:
			c = i + 1
		ans += c
	print(ans)
	t -= 1


from itertools import combinations
for _ in range(int(input())):
	n = int(input())
	c = 0
	(string, to_find) = input().split()
	tot = n * (n + 1) // 2
	l = string.split(to_find)
	for i in l:
		tot -= len(i) * (len(i) + 1) // 2
	print(tot)


def num(x):
	return x * (x + 1) // 2
for _ in range(int(input())):
	n = int(input())
	(s, x) = input().split()
	c = 0
	tot = num(n)
	l = s.split(x)
	for i in l:
		tot -= num(len(i))
	print(tot)