On vous donne deux chaînes de caractères $s$ et $t$, toutes deux composées de lettres minuscules.

Soit $s_{l,r}$ la sous-chaîne de $s$ allant de son $l$-ième caractère à son $r$-ième caractère, de longueur $L = r - l + 1$. On dit que $t$ apparaît sur le cercle de $s_{l,r}$ si et seulement s'il existe une position de départ $p$ ($0 \le p < L$) telle que pour tout $0 \le k < |t|$, on ait $s_{l,r}[(p + k) \bmod L] = t[k]$. Si $L < |t|$, alors on considère que $t$ n'apparaît pas sur le cercle de $s_{l,r}$.

Comptez combien de paires distinctes $(l, r)$ vérifient que $t$ apparaît sur le cercle de $s_{l,r}$.

Entrée

Chaque fichier de test contient plusieurs cas de test. La première ligne contient le nombre de cas de test $T$ ($1 \le T \le 2 \times 10^5$). La description des cas de test suit.

La première ligne de chaque cas de test contient une chaîne $s$ ($1 \le |s| \le 2 \times 10^5$).

La deuxième ligne contient une chaîne $t$ ($1 \le |t| \le 2 \times 10^5$).

Il est garanti que toutes les chaînes sont composées de lettres minuscules.

Pour chaque fichier de test, il est garanti que la somme des $|s|$ sur tous les cas de test ne dépasse pas $2 \times 10^5$, et que la somme des $|t|$ sur tous les cas de test ne dépasse pas $2 \times 10^5$.

Sortie

Pour chaque cas de test, affichez un entier sur une seule ligne, représentant le nombre de paires $(l, r)$ qui satisfont la condition.

Exemples

Entrée 1

3
cabcccabc
ccabcc
bcdabc
abcd
aaaxaaaxaaa
axaaaxaa

Sortie 1

3
3
10

Entrée 2

4
aaaaaaaaa
a
abacab
caba
baaabaab
aabaaab
bbabbbabb
bbbabbb

Sortie 2

45
4
2
3