Given two strings S and T where T is a subsequence of S, you need to find the number of pairs of indices $(i, j)$, where $i \le j$ , such that if we delete a non-empty substring $S[i... j]$ from string S and concatenate the remaining two parts, string T still remains a subsequence of string S. Note that we consider each pair of indices $(i, j)$ independent of all other pairs.

Input Format:
The first line of the input consists of a single integer t, denoting the number of test cases.
The first line of each test case consists of string S.
The second line of each test case consists of string T.

Output Format:
For each test case, print the required answer in a separate line.

Input Constraints:

• $1 \le t \le 10$
• $1 \le |S| \le 10^{5}$
• $1 \le |T| \le |S|$
• Both strings S and T contain only lowercase English alphabets.