Givet två strängar $s$ och $t$, som båda består av små bokstäver.

Låt $s_{l,r}$ vara delsträngen av $s$ från dess $l$-te tecken till dess $r$-te tecken med längd $L = r - l + 1$. Vi säger att $t$ förekommer på cirkeln av $s_{l,r}$ om och endast om det finns en startposition $p$ ($0 \le p < L$) sådan att vi för alla $0 \le k < |t|$ har $s_{l,r}[(p + k) \bmod L] = t[k]$. Om $L < |t|$ anses $t$ inte förekomma på cirkeln av $s_{l,r}$.

Räkna hur många distinkta par $(l, r)$ som uppfyller att $t$ förekommer på cirkeln av $s_{l,r}$.

Indata

Varje testfil innehåller flera testfall. Den första raden innehåller antalet testfall $T$ ($1 \le T \le 2 \times 10^5$). Beskrivningen av testfallen följer.

Den första raden i varje testfall innehåller en sträng $s$ ($1 \le |s| \le 2 \times 10^5$).

Den andra raden innehåller en sträng $t$ ($1 \le |t| \le 2 \times 10^5$).

Det garanteras att alla strängar består av små bokstäver.

För varje testfil garanteras det att summan av $|s|$ över alla testfall inte överstiger $2 \times 10^5$, och att summan av $|t|$ över alla testfall inte överstiger $2 \times 10^5$.

Utdata

För varje testfall, skriv ut ett heltal på en enda rad, som representerar antalet par $(l, r)$ som uppfyller villkoret.

Exempel

Indata 1

3
cabcccabc
ccabcc
bcdabc
abcd
aaaxaaaxaaa
axaaaxaa

Utdata 1

3
3
10

Indata 2

4
aaaaaaaaa
a
abacab
caba
baaabaab
aabaaab
bbabbbabb
bbbabbb

Utdata 2

45
4
2
3