该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题面_2024“钉耙编程”中国大学生算法设计超级联赛(1)-题目集.pdf

定义字符串 $S=S_0+\dots+S_{n-1}$ 循环位移 $k$ 次为

$S(k) = S_{k\mod n}+\dots + S_{n-1} + S_0 + \dots + S_{(k-1) \mod n}$。

定义 $[A] = \set{A(k), k \in \mathbb N}$.

给出 $T$ 组串 $A, B$，询问 $B$ 有多少个子串在 $[A]$ 中。

Input

第一行一个 $T$ 表示输入组数。

接下来每行两个字符串，表示 $A$ 和 $B$，保证 $|A| \leq |B|$。

保证 $\sum |B| \leq 1048576.$，并且字符串均由大写字母组成。

Output

输出 $T$ 行，每行一个数表示答案。

3
AN MANTLEFAN
MVP XPTIJMVPMVP
CJMR JDRCJMRAJMRCJMGC

2
4
5

第一个样例：MANTLEFAN,MANTLEFAN

第三个样例：JDRCJMRAJMRCJMGC,JDRCJMRAJMRCJMGC,JDRCJMRAJMRCJMGC,JDRCJMRAJMRCJMGC,JDRCJMRAJMRCJMGC