Problem 28482 -- dna

28482: dna

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 4  Solved: 1
[Submit][Status][Web Board][Creator:][下载FPS0元][添加到购物车][下载测试数据0元][13550kb]

Description

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

Input

第一行有一个数T,表示有几组数据 

每组数据第一行一个长度不超过105的碱基序列S0 

每组数据第二行一个长度不超过105的吃藕基因序列S

Output

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

Sample Input

1
ATCGCCCTA
CTTCA

Sample Output

2

HINT


对于20%的数据,S0,S的长度不超过104 



对于100%的数据,S0,S的长度不超过105



对于所有数据0 < T ≤ 10

Source

[Submit][Status]