Cho hai xâu $s$ và $t$, cả hai đều chỉ gồm các chữ cái thường.

Gọi $s_{l,r}$ là xâu con của $s$ từ ký tự thứ $l$ đến ký tự thứ $r$ với độ dài $L = r - l + 1$. Ta nói $t$ xuất hiện trên vòng tròn của $s_{l,r}$ khi và chỉ khi tồn tại một vị trí bắt đầu $p$ ($0 \le p < L$) sao cho với mọi $0 \le k < |t|$, ta có $s_{l,r}[(p + k) \bmod L] = t[k]$. Nếu $L < |t|$, thì $t$ được coi là không xuất hiện trên vòng tròn của $s_{l,r}$.

Hãy đếm xem có bao nhiêu cặp $(l, r)$ phân biệt thỏa mãn $t$ xuất hiện trên vòng tròn của $s_{l,r}$.

Dữ liệu vào

Mỗi tệp kiểm tra chứa nhiều bộ dữ liệu. Dòng đầu tiên chứa số lượng bộ dữ liệu $T$ ($1 \le T \le 2 \times 10^5$). Mô tả của các bộ dữ liệu theo sau.

Dòng đầu tiên của mỗi bộ dữ liệu chứa một xâu $s$ ($1 \le |s| \le 2 \times 10^5$).

Dòng thứ hai chứa một xâu $t$ ($1 \le |t| \le 2 \times 10^5$).

Dữ liệu đảm bảo tất cả các xâu đều chỉ gồm các chữ cái thường.

Đối với mỗi tệp kiểm tra, dữ liệu đảm bảo tổng của $|s|$ qua tất cả các bộ dữ liệu không vượt quá $2 \times 10^5$, và tổng của $|t|$ qua tất cả các bộ dữ liệu không vượt quá $2 \times 10^5$.

Kết quả

Với mỗi bộ dữ liệu, hãy in ra một số nguyên trên một dòng duy nhất, biểu thị số lượng cặp $(l, r)$ thỏa mãn điều kiện.

Ví dụ

Dữ liệu vào 1

3
cabcccabc
ccabcc
bcdabc
abcd
aaaxaaaxaaa
axaaaxaa

Kết quả 1

3
3
10

Dữ liệu vào 2

4
aaaaaaaaa
a
abacab
caba
baaabaab
aabaaab
bbabbbabb
bbbabbb

Kết quả 2

45
4
2
3