Дано два рядки $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