Кіші әріптерден тұратын екі $s$ және $t$ жолдары берілген.

$s_{l,r}$ арқылы $s$ жолының $l$-ші таңбасынан $r$-ші таңбасына дейінгі ұзындығы $L = r - l + 1$ болатын ішкі жолын белгілейік. Егер барлық $0 \le k < |t|$ үшін $s_{l,r}[(p + k) \bmod L] = t[k]$ орындалатындай бастапқы позиция $p$ ($0 \le p < L$) табылса және тек сонда ғана, $t$ жолы $s_{l,r}$ шеңберінде кездеседі деп айтамыз. Егер $L < |t|$ болса, онда $t$ жолы $s_{l,r}$ шеңберінде кездеспейді деп есептеледі.

$t$ жолы $s_{l,r}$ шеңберінде кездесетіндей қанша әртүрлі $(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