Gitt to strenger $s$ og $t$, som begge består av små bokstaver.

La $s_{l,r}$ være delstrengen av $s$ fra dens $l$-te tegn til dens $r$-te tegn med lengde $L = r - l + 1$. Vi sier at $t$ forekommer på sirkelen til $s_{l,r}$ hvis og bare hvis det finnes en startposisjon $p$ ($0 \le p < L$) slik at vi for alle $0 \le k < |t|$ har $s_{l,r}[(p + k) \bmod L] = t[k]$. Hvis $L < |t|$, regnes $t$ for ikke å forekomme på sirkelen til $s_{l,r}$.

Tell hvor mange forskjellige par $(l, r)$ som oppfyller at $t$ forekommer på sirkelen til $s_{l,r}$.

Inndata

Hver testfil inneholder flere testtilfeller. Den første linjen inneholder antallet testtilfeller $T$ ($1 \le T \le 2 \times 10^5$). Beskrivelsen av testtilfellene følger.

Den første linjen i hvert testtilfelle inneholder en streng $s$ ($1 \le |s| \le 2 \times 10^5$).

Den andre linjen inneholder en streng $t$ ($1 \le |t| \le 2 \times 10^5$).

Det er garantert at alle strenger består av små bokstaver.

For hver testfil er det garantert at summen av $|s|$ over alle testtilfeller ikke overstiger $2 \times 10^5$, og at summen av $|t|$ over alle testtilfeller ikke overstiger $2 \times 10^5$.

Utdata

For hvert testtilfelle, skriv ut ett heltall på en enkelt linje, som representerer antallet par $(l, r)$ som oppfyller betingelsen.

Eksempler

Inndata 1

3
cabcccabc
ccabcc
bcdabc
abcd
aaaxaaaxaaa
axaaaxaa

Utdata 1

3
3
10

Inndata 2

4
aaaaaaaaa
a
abacab
caba
baaabaab
aabaaab
bbabbbabb
bbbabbb

Utdata 2

45
4
2
3