P5256 [JSOI2013] Programming Assignment

Consider the following two pieces of code. It is easy to see that they are actually the same. #### Code 1 ```cpp int i, j; i = 3; j = i + 1; ``` #### Code 2 ```cpp 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 ```cpp a = 3; b = 3; ``` #### Code 4 ```cpp 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.

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 $Q$ lines in total. Each line contains an integer, representing the number of occurrences of the corresponding code fragment.

#### 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