Description

Researchers at the Biology Institute of Garitun University discovered a gene sequence $S$ that determines whether a person likes eating lotus root. Any DNA segment with this sequence exhibits the "likes lotus root" trait. Moreover, they found that for the base sequence $S$, modifying at most $3$ bases still results in the trait. Now the researchers want to locate this gene on a DNA strand $S_0$. Therefore, you need to count, on the DNA sequence $S_0$ of a person who exhibits the trait, how many contiguous substrings could be this gene, i.e., how many contiguous substrings of $S_0$ can be changed into $S$ by modifying at most three letters.

Input Format

The first line contains an integer $T$, the number of test cases.

For each test case, the first line contains a base sequence $S_0$ of length not exceeding $10^5$.

The second line contains the "lotus-root gene" sequence $S$ of length not exceeding $10^5$.

Output Format

Output $T$ lines. The $i$-th line indicates, in the $i$-th test case, how many contiguous substrings in $S_0$ of the same length as $S$ could be a base sequence exhibiting the "likes lotus root" trait.

1
ATCGCCCTA
CTTCA

2

Hint

For $20\%$ of the testdata, the lengths of $S_0$ and $S$ do not exceed $10^4$.

For $100\%$ of the testdata, the lengths of $S_0$ and $S$ do not exceed $10^5$, $0\lt T\leq 10$.

Note: DNA base sequences only contain the four characters A, T, C, and G.

Translated by ChatGPT 5