กำหนดสตริงสองสายคือ $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