Date due stringhe $s$ e $t$, entrambe composte da lettere minuscole.

Sia $s_{l,r}$ la sottostringa di $s$ dal suo $l$-esimo carattere al suo $r$-esimo carattere con lunghezza $L = r - l + 1$. Diciamo che $t$ appare sul cerchio di $s_{l,r}$ se e solo se esiste una posizione iniziale $p$ ($0 \le p < L$) tale che per tutti gli $0 \le k < |t|$, si ha $s_{l,r}[(p + k) \bmod L] = t[k]$. Se $L < |t|$, allora si considera che $t$ non appaia sul cerchio di $s_{l,r}$.

Conta quante coppie distinte $(l, r)$ soddisfano la condizione che $t$ appaia sul cerchio di $s_{l,r}$.

Input

Ogni file di test contiene più casi di test. La prima riga contiene il numero di casi di test $T$ ($1 \le T \le 2 \times 10^5$). Segue la descrizione dei casi di test.

La prima riga di ogni caso di test contiene una stringa $s$ ($1 \le |s| \le 2 \times 10^5$).

La seconda riga contiene una stringa $t$ ($1 \le |t| \le 2 \times 10^5$).

È garantito che tutte le stringhe sono composte da lettere minuscole.

Per ogni file di test, è garantito che la somma di $|s|$ su tutti i casi di test non supera $2 \times 10^5$, e la somma di $|t|$ su tutti i casi di test non supera $2 \times 10^5$.

Output

Per ogni caso di test, stampa un intero su una singola riga, che rappresenta il numero di coppie $(l, r)$ che soddisfano la condizione.

Esempi

Input 1

3
cabcccabc
ccabcc
bcdabc
abcd
aaaxaaaxaaa
axaaaxaa

Output 1

3
3
10

Input 2

4
aaaaaaaaa
a
abacab
caba
baaabaab
aabaaab
bbabbbabb
bbbabbb

Output 2

45
4
2
3