Даны две строки $s$ и $t$, состоящие из строчных букв.

Пусть $s_{l,r}$ — подстрока строки $s$ с её $l$-го по $r$-й символ длины $L = r - l + 1$. Будем говорить, что $t$ входит по кругу в $s_{l,r}$, тогда и только тогда, когда существует начальная позиция $p$ ($0 \le p < L$) такая, что для всех $0 \le k < |t|$ выполняется $s_{l,r}[(p + k) \bmod L] = t[k]$. Если $L < |t|$, то считается, что $t$ не входит по кругу в $s_{l,r}$.

Посчитайте, сколько различных пар $(l, r)$ удовлетворяют тому, что $t$ входит по кругу в $s_{l,r}$.

Входные данные

Каждый тестовый файл содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $T$ ($1 \le T \le 2 \times 10^5$). Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит строку $s$ ($1 \le |s| \le 2 \times 10^5$).

Вторая строка содержит строку $t$ ($1 \le |t| \le 2 \times 10^5$).

Гарантируется, что все строки состоят из строчных букв.

Для каждого тестового файла гарантируется, что сумма $|s|$ по всем наборам входных данных не превышает $2 \times 10^5$, и сумма $|t|$ по всем наборам входных данных не превышает $2 \times 10^5$.

Выходные данные

Для каждого набора входных данных выведите в отдельной строке одно целое число — количество пар $(l, r)$, удовлетворяющих условию.

Примеры

Входные данные 1

3
cabcccabc
ccabcc
bcdabc
abcd
aaaxaaaxaaa
axaaaxaa

Выходные данные 1

3
3
10

Входные данные 2

4
aaaaaaaaa
a
abacab
caba
baaabaab
aabaaab
bbabbbabb
bbbabbb

Выходные данные 2

45
4
2
3