Problem Description

Consider the following two pieces of code. It is easy to see that they are actually the same.

Code 1

int i, j;
i = 3;
j = i + 1;

Code 2

int a, i;
a = 3;
i = a + 1;

This is because the only difference between these two pieces of code is that they rename the variables. For example, i in the first code becomes a in the second code, and j in the first code becomes i in the second code. All other constants, such as 3 and 1, and other keywords and operators, such as int, +, and ;, do not change.

However, for the following code fragments, we cannot simply treat them as the same, because this is not a simple replacement and it can lead to different computation results.

Code 3

a = 3;
b = 3;

Code 4

c = 3;
c = 3; 

To simplify the problem, we use uppercase letters to represent all non-variable symbols, such as keywords and constants.

Suppose we use the following substitution table:

Then the two similar code pieces given at the beginning can be written as AiBjCiDECjDiFGC and AaBiCaDECiDaFGC, respectively.

In other words, we consider these two pieces of code to be the same.

Now please write a program to handle several such code similarity detection queries: given a full code string and a shorter code fragment, find how many times this fragment appears in the full code (the occurrence positions may overlap).

For simplicity, we assume that at most the $26$ variables $\text a\sim \text z$ may appear in the program, and at most the $26$ non-variable symbols $\text A\sim \text Z$ may appear.

Input Format

The first line contains an integer $Q$, indicating that this testdata contains $Q$ queries in total.

The next $2Q$ lines describe the queries, with every two lines forming one query.

In each query, the first line contains a string $S$, representing the full code, and the second line contains a string $T$, representing the code fragment whose number of occurrences needs to be checked.

Output Format

Output $Q$ lines in total. Each line contains an integer, representing the number of occurrences of the corresponding code fragment.

3
AiBjCiDECjDiFGC
AaBiCaDECiDaFGC
cDEcDEbDE
aDEbDE
ccddef
aab

1
1
2

Hint

Sample Explanation

In the first two samples, the code fragments are the examples given in the statement. In the third sample, the fragments in the full code $S$ that are the same as the code fragment $T$ are: ccd and dde.

Constraints

$Q<=3,|T|<=10^5,|S|<=10^6$

Translated by ChatGPT 5