题目描述

加里敦大学的生物研究所，发现了决定人喜不喜欢吃藕的基因序列 $S$,有这个序列的碱基序列就会表现出喜欢吃藕的性状，但是研究人员发现对碱基序列 $S$，任意修改其中不超过 $3$ 个碱基，依然能够表现出吃藕的性状。现在研究人员想知道这个基因在 DNA 链 $S_0$ 上的位置。所以你需要统计在一个表现出吃藕性状的人的 DNA 序列 $S_0$ 上，有多少个连续子串可能是该基因，即有多少个 $S_0$ 的连续子串修改小于等于三个字母能够变成 $S$。

输入格式

第一行有一个整数 $T$，表示有几组数据。

每组数据第一行一个长度不超过 $10^5$ 的碱基序列 $S_0$。

每组数据第二行一个长度不超过 $10^5$ 的吃藕基因序列 $S$。

输出格式

共 $T$ 行，第 $i$ 行表示第 $i$ 组数据中，在 $S_0$ 中有多少个与 $S$ 等长的连续子串可能是表现吃藕性状的碱基序列。

1
ATCGCCCTA
CTTCA

2

数据范围与提示

• 对于 $20\%$ 的数据，$S_0,S$ 的长度不超过 $10^4$。
• 对于 $100\%$ 的数据，$S_0,S$ 的长度不超过 $10^5$，$0\lt T\leq 10$。

注：DNA 碱基序列只有 ATCG 四种字符。