أُعطيت سلسلتين نصيتين $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