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

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

3
AN MANTLEFAN
MVP XPTIJMVPMVP
CJMR JDRCJMRAJMRCJMGC

2
4
5

Hint

第一个样例：M`AN`TLEFAN,MANTLEF`AN`第三个样例：JD`RCJM`RAJMRCJMGC,JDR`CJMR`AJMRCJMGC,JDRCJMRA`JMRC`JMGC,JDRCJMRAJ`MRCJ`MGC,JDRCJMRAJM`RCJM`GC