[TJOI2017] DNA

题目描述

加里敦大学的生物研究所,发现了决定人喜不喜欢吃藕的基因序列 $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

1
ATCGCCCTA
CTTCA

输出样例 #1

2

说明

对于 $20\%$ 的数据,$S_0,S$ 的长度不超过 $10^4$。 对于 $100\%$ 的数据,$S_0,S$ 的长度不超过 $10^5$,$0\lt T\leq 10$。 注:DNA 碱基序列只有 ATCG 四种字符。