Dane są dwa napisy $s$ oraz $t$, oba składające się z małych liter.

Niech $s_{l,r}$ będzie podciągiem (spójnym podnapisem) napisu $s$ od jego $l$-tego znaku do $r$-tego znaku o długości $L = r - l + 1$. Mówimy, że $t$ występuje na okręgu $s_{l,r}$ wtedy i tylko wtedy, gdy istnieje pozycja początkowa $p$ ($0 \le p < L$) taka, że dla wszystkich $0 \le k < |t|$ zachodzi $s_{l,r}[(p + k) \bmod L] = t[k]$. Jeśli $L < |t|$, to uznajemy, że $t$ nie występuje na okręgu $s_{l,r}$.

Policz, ile różnych par $(l, r)$ spełnia warunek, że $t$ występuje na okręgu $s_{l,r}$.

Wejście

Każdy plik testowy zawiera wiele przypadków testowych. Pierwszy wiersz zawiera liczbę przypadków testowych $T$ ($1 \le T \le 2 \times 10^5$). Poniżej następuje opis przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera napis $s$ ($1 \le |s| \le 2 \times 10^5$).

Drugi wiersz zawiera napis $t$ ($1 \le |t| \le 2 \times 10^5$).

Gwarantuje się, że wszystkie napisy składają się z małych liter.

Dla każdego pliku testowego gwarantuje się, że suma $|s|$ po wszystkich przypadkach testowych nie przekracza $2 \times 10^5$, a suma $|t|$ po wszystkich przypadkach testowych nie przekracza $2 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz w pojedynczym wierszu jedną liczbę całkowitą, oznaczającą liczbę par $(l, r)$ spełniających warunek.

Przykłady

Wejście 1

3
cabcccabc
ccabcc
bcdabc
abcd
aaaxaaaxaaa
axaaaxaa

Wyjście 1

3
3
10

Wejście 2

4
aaaaaaaaa
a
abacab
caba
baaabaab
aabaaab
bbabbbabb
bbbabbb

Wyjście 2

45
4
2
3