英小文字からなる $2$ つの文字列 $s$ と $t$ が与えられます。

$s_{l,r}$ を、$s$ の $l$ 文字目から $r$ 文字目までの長さ $L = r - l + 1$ の部分文字列とします。ある開始位置 $p$ ($0 \le p < L$) が存在して、すべての $0 \le k < |t|$ に対して $s_{l,r}[(p + k) \bmod L] = t[k]$ が成り立つとき、かつそのときに限り、$t$ は $s_{l,r}$ の円環上に現れるといいます。ただし、$L < |t|$ の場合は、$t$ は $s_{l,r}$ の円環上に現れないものとみなします。

$t$ が $s_{l,r}$ の円環上に現れるような異なる組 $(l, r)$ がいくつあるか数えてください。

入力

各テストファイルは複数のテストケースを含みます。$1$ 行目にはテストケースの数 $T$ ($1 \le T \le 2 \times 10^5$) が与えられます。続けて各テストケースの記述が与えられます。

各テストケースの $1$ 行目には文字列 $s$ ($1 \le |s| \le 2 \times 10^5$) が与えられます。

$2$ 行目には文字列 $t$ ($1 \le |t| \le 2 \times 10^5$) が与えられます。

すべての文字列は英小文字のみからなることが保証されています。

各テストファイルについて、すべてのテストケースにわたる $|s|$ の総和は $2 \times 10^5$ を超えず、$|t|$ の総和も $2 \times 10^5$ を超えないことが保証されています。

出力

各テストケースについて、条件を満たす組 $(l, r)$ の個数を表す整数を $1$ 行に出力してください。

入力例

入力 1

3
cabcccabc
ccabcc
bcdabc
abcd
aaaxaaaxaaa
axaaaxaa

出力 1

3
3
10

入力 2

4
aaaaaaaaa
a
abacab
caba
baaabaab
aabaaab
bbabbbabb
bbbabbb

出力 2

45
4
2
3