Gegeben sind zwei Zeichenketten $s$ und $t$, die beide aus Kleinbuchstaben bestehen.

Sei $s_{l,r}$ die Teilzeichenkette von $s$ vom $l$-ten Zeichen bis zum $r$-ten Zeichen mit der Länge $L = r - l + 1$. Wir sagen, dass $t$ auf dem Kreis von $s_{l,r}$ vorkommt, genau dann, wenn eine Startposition $p$ ($0 \le p < L$) existiert, sodass für alle $0 \le k < |t|$ die Gleichung $s_{l,r}[(p + k) \bmod L] = t[k]$ gilt. Falls $L < |t|$ ist, gilt $t$ als nicht auf dem Kreis von $s_{l,r}$ vorkommend.

Zähle, wie viele verschiedene Paare $(l, r)$ die Bedingung erfüllen, dass $t$ auf dem Kreis von $s_{l,r}$ vorkommt.

Eingabe

Jede Testdatei enthält mehrere Testfälle. Die erste Zeile enthält die Anzahl der Testfälle $T$ ($1 \le T \le 2 \times 10^5$). Es folgt die Beschreibung der Testfälle.

Die erste Zeile jedes Testfalls enthält eine Zeichenkette $s$ ($1 \le |s| \le 2 \times 10^5$).

Die zweite Zeile enthält eine Zeichenkette $t$ ($1 \le |t| \le 2 \times 10^5$).

Es wird garantiert, dass alle Zeichenketten aus Kleinbuchstaben bestehen.

Für jede Testdatei wird garantiert, dass die Summe von $|s|$ über alle Testfälle hinweg $2 \times 10^5$ nicht überschreitet und die Summe von $|t|$ über alle Testfälle hinweg $2 \times 10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine ganze Zahl in einer einzigen Zeile aus, welche die Anzahl der Paare $(l, r)$ darstellt, die die Bedingung erfüllen.

Beispiele

Eingabe 1

3
cabcccabc
ccabcc
bcdabc
abcd
aaaxaaaxaaa
axaaaxaa

Ausgabe 1

3
3
10

Eingabe 2

4
aaaaaaaaa
a
abacab
caba
baaabaab
aabaaab
bbabbbabb
bbbabbb

Ausgabe 2

45
4
2
3