Gefnir eru tveir strengir $s$ og $t$, sem báðir samanstanda af lágstöfum.

Látum $s_{l,r}$ vera hlutstreng $s$ frá $l$-ta staf hans til $r$-ta stafs hans með lengd $L = r - l + 1$. Við segjum að $t$ komi fyrir á hring $s_{l,r}$ ef og aðeins ef til er upphafsstaða $p$ ($0 \le p < L$) þannig að fyrir öll $0 \le k < |t|$ gildir $s_{l,r}[(p + k) \bmod L] = t[k]$. Ef $L < |t|$, þá telst $t$ ekki koma fyrir á hring $s_{l,r}$.

Teldu hversu mörg ólík pör $(l, r)$ uppfylla að $t$ kemur fyrir á hring $s_{l,r}$.

Inntak

Hver prófunarskrá inniheldur mörg prófunartilvik. Fyrsta línan inniheldur fjölda prófunartilvika $T$ ($1 \le T \le 2 \times 10^5$). Lýsing á prófunartilvikunum fylgir á eftir.

Fyrsta línan í hverju prófunartilviki inniheldur streng $s$ ($1 \le |s| \le 2 \times 10^5$).

Önnur línan inniheldur streng $t$ ($1 \le |t| \le 2 \times 10^5$).

Það er tryggt að allir strengir samanstandi af lágstöfum.

Fyrir hverja prófunarskrá er tryggt að summa $|s|$ yfir öll prófunartilvik fari ekki yfir $2 \times 10^5$, og summa $|t|$ yfir öll prófunartilvik fari ekki yfir $2 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina heiltölu á stakri línu, sem táknar fjölda para $(l, r)$ sem uppfylla skilyrðið.

Dæmi

Inntak 1

3
cabcccabc
ccabcc
bcdabc
abcd
aaaxaaaxaaa
axaaaxaa

Úttak 1

3
3
10

Inntak 2

4
aaaaaaaaa
a
abacab
caba
baaabaab
aabaaab
bbabbbabb
bbbabbb

Úttak 2

45
4
2
3