Biologists at the University of Cambridge have discovered a gene sequence $S$ that determines whether a person likes eating lotus roots. Any sequence of bases that is similar to $S$ will also exhibit the trait of liking lotus roots. A sequence is considered similar to $S$ if it can be transformed into $S$ by changing at most 3 bases. You are tasked with finding the locations of these genes in a DNA chain $S_0$. Specifically, you need to count how many contiguous substrings of $S_0$ with the same length as $S$ can be transformed into $S$ by changing at most 3 bases.

Input

The first line contains an integer $T$, representing the number of test cases. For each test case, the first line contains a base sequence $S_0$ with a length not exceeding $10^5$. The second line contains a gene sequence $S$ with a length not exceeding $10^5$.

Output

Output $T$ lines. The $i$-th line should contain the number of contiguous substrings in $S_0$ that have the same length as $S$ and are similar to $S$.

Constraints

• For 20% of the data, the lengths of $S_0$ and $S$ do not exceed $10^4$.
• For 100% of the data, the lengths of $S_0$ and $S$ do not exceed $10^5$.
• For all data, $0 < T \le 10$.

Examples

Input 1

1
ATCGCCCTA
CTTCA

Output 1

2