Diberikan dua string $s$ dan $t$, yang keduanya terdiri dari huruf-huruf kecil.

Misalkan $s_{l,r}$ adalah substring dari $s$ mulai dari karakter ke-$l$ hingga karakter ke-$r$ dengan panjang $L = r - l + 1$. Kita katakan bahwa $t$ muncul pada lingkaran dari $s_{l,r}$ jika dan hanya jika terdapat posisi awal $p$ ($0 \le p < L$) sedemikian sehingga untuk semua $0 \le k < |t|$, berlaku $s_{l,r}[(p + k) \bmod L] = t[k]$. Jika $L < |t|$, maka $t$ dianggap tidak muncul pada lingkaran dari $s_{l,r}$.

Hitunglah berapa banyak pasangan $(l, r)$ berbeda yang memenuhi bahwa $t$ muncul pada lingkaran dari $s_{l,r}$.

Masukan

Setiap berkas uji berisi beberapa kasus uji. Baris pertama berisi jumlah kasus uji $T$ ($1 \le T \le 2 \times 10^5$). Deskripsi dari masing-masing kasus uji menyusul setelahnya.

Baris pertama dari setiap kasus uji berisi sebuah string $s$ ($1 \le |s| \le 2 \times 10^5$).

Baris kedua berisi sebuah string $t$ ($1 \le |t| \le 2 \times 10^5$).

Dijamin bahwa semua string terdiri dari huruf-huruf kecil.

Untuk setiap berkas uji, dijamin bahwa jumlah $|s|$ di seluruh kasus uji tidak melebihi $2 \times 10^5$, dan jumlah $|t|$ di seluruh kasus uji tidak melebihi $2 \times 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu bilangan bulat dalam satu baris, yang menyatakan jumlah pasangan $(l, r)$ yang memenuhi kondisi tersebut.

Contoh

Masukan 1

3
cabcccabc
ccabcc
bcdabc
abcd
aaaxaaaxaaa
axaaaxaa

Keluaran 1

3
3
10

Masukan 2

4
aaaaaaaaa
a
abacab
caba
baaabaab
aabaaab
bbabbbabb
bbbabbb

Keluaran 2

45
4
2
3