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".

见题面

见题面