题目描述

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

定义 $[A]=\{A(k),k \in \text{N}\}$。

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

输入格式

第一行 $1$ 个整数 $T$ ($1\le T \le 100$)，代表测试样例个数。

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

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

输出格式

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

输入样例

3
AN MANTLEFAN
MVP XPTIJMVPMVP
CJMR JDRCJMRAJMRCJMGC

输出样例

2
4
5

提示

第一个样例：

MANTLEFAN

MANTLEFAN

第三个样例：

JDRCJMRAJMRCJMGC

JDRCJMRAJMRCJMGC

JDRCJMRAJMRCJMGC

JDRCJMRAJMRCJMGC

JDRCJMRAJMRCJMGC