소문자로만 이루어진 두 문자열 $s$와 $t$가 주어집니다.

$s_{l,r}$를 $s$의 $l$번째 문자부터 $r$번째 문자까지로 이루어진 길이 $L = r - l + 1$인 부분 문자열이라고 합시다. 어떤 시작 위치 $p$ ($0 \le p < L$)가 존재하여 모든 $0 \le k < |t|$에 대해 $s_{l,r}[(p + k) \bmod L] = t[k]$를 만족할 때, 그리고 그때에만 $t$가 $s_{l,r}$의 원(circle) 위에 나타난다고 말합니다. 만약 $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