נתונות שתי מחרוזות $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