#P18051. Circular Matching

Circular Matching

Circular Matching

给定两个仅含小写英文字母的字符串 s,ts,t。

对于 ss 的子串 s[l…r]s[l\ldots r],令其长度为 L=r−l+1L=r-l+1,并将该子串首尾相接成一个环。只有 L≥∣t∣L\ge |t| 时,才可能认为 tt 出现在该环上。

更准确地说,若存在整数 pp,0≤p<L0\le p<L,使得对于每个 0≤k<∣t∣0\le k<|t|,均有

sl+(p+k) mod L=tk+1,s_{l+(p+k)\bmod L}=t_{k+1},

则称这对 (l,r)(l,r) 合法。

求合法的下标对 (l,r)(l,r) 的数量。即使两个子串的内容相同,只要位置不同,也要分别计数。

输入格式

第一行整数 TT,1≤T≤2×1051\le T\le2\times10^5。每个用例两行,分别给出 ss 和 tt。

1≤∣s∣,∣t∣≤2×1051\le |s|,|t|\le2\times10^5。一个输入文件内,所有 ∣s∣|s| 的和、所有 ∣t∣|t| 的和分别不超过 2×1052\times10^5。

输出格式

每个用例输出一行一个整数,表示合法下标对的数量。

样例

输入:

3
cabcccabc
ccabcc
bcdabc
abcd
aaaxaaaxaaa
axaaaxaa

输出:

3
3
10