Annetaan kaksi merkkijonoa $s$ ja $t$, jotka molemmat koostuvat pienaakkosista.

Olkoon $s_{l,r}$ merkkijonon $s$ osamerkkijono sen $l$-nnestä merkistä sen $r$-nteen merkkiin, jonka pituus on $L = r - l + 1$. Sanomme, että $t$ esiintyy merkkijonon $s_{l,r}$ kehällä, jos ja vain jos on olemassa aloituskohta $p$ ($0 \le p < L$) siten, että kaikilla $0 \le k < |t|$ pätee $s_{l,r}[(p + k) \bmod L] = t[k]$. Jos $L < |t|$, katsotaan, että $t$ ei esiinny merkkijonon $s_{l,r}$ kehällä.

Laske, kuinka moni eri pari $(l, r)$ toteuttaa ehdon, että $t$ esiintyy merkkijonon $s_{l,r}$ kehällä.

Syöte

Jokainen testitiedosto sisältää useita testitapauksia. Ensimmäinen rivi sisältää testitapausten lukumäärän $T$ ($1 \le T \le 2 \times 10^5$). Seuraavaksi on testitapausten kuvaus.

Jokaisen testitapauksen ensimmäinen rivi sisältää merkkijonon $s$ ($1 \le |s| \le 2 \times 10^5$).

Toinen rivi sisältää merkkijonon $t$ ($1 \le |t| \le 2 \times 10^5$).

On taattu, että kaikki merkkijonot koostuvat pienaakkosista.

Jokaisessa testitiedostossa on taattu, että pituuksien $|s|$ summa yli kaikkien testitapausten ei ylitä $2 \times 10^5$ ja pituuksien $|t|$ summa yli kaikkien testitapausten ei ylitä $2 \times 10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle omalle rivilleen yksi kokonaisluku, joka ilmaisee ehdon toteuttavien parien $(l, r)$ lukumäärän.

Esimerkit

Syöte 1

3
cabcccabc
ccabcc
bcdabc
abcd
aaaxaaaxaaa
axaaaxaa

Tuloste 1

3
3
10

Syöte 2

4
aaaaaaaaa
a
abacab
caba
baaabaab
aabaaab
bbabbbabb
bbbabbb

Tuloste 2

45
4
2
3