給定兩個皆由小寫字母組成的字串 $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