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