循环位移

Problem Description

请注意本题特殊的空间限制！

定义字符串 $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$ 行，每行一个数表示答案。

Sample Input

3
AN MANTLEFAN
MVP XPTIJMVPMVP
CJMR JDRCJMRAJMRCJMGC

Sample Output

2
4
5

Hint

第一个样例：MANTLEFAN,MANTLEFAN

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

Source

2024“钉耙编程”中国大学生算法设计超级联赛（1）