Given two strings $s$ and $t$, both consisting of lowercase letters.

Let $s_{l,r}$ be the substring of $s$ from its $l$-th character to its $r$-th character with length $L = r - l + 1$. We say that $t$ appears on the circle of $s_{l,r}$ if and only if there exists a starting position $p$ ($0 \le p < L$) such that for all $0 \le k < |t|$, we have $s_{l,r}[(p + k) \bmod L] = t[k]$. If $L < |t|$, then $t$ is considered not to appear on the circle of $s_{l,r}$.

Count how many distinct pairs $(l, r)$ satisfy that $t$ appears on the circle of $s_{l,r}$.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 2 \times 10^5$). The description of the test cases follows.

The first line of each test case contains a string $s$ ($1 \le |s| \le 2 \times 10^5$).

The second line contains a string $t$ ($1 \le |t| \le 2 \times 10^5$).

It is guaranteed that all strings consist of lowercase letters.

For each test file, it is guaranteed that the sum of $|s|$ over all test cases does not exceed $2 \times 10^5$, and the sum of $|t|$ over all test cases does not exceed $2 \times 10^5$.

Output

For each test case, output one integer on a single line, representing the number of pairs $(l, r)$ that satisfy the condition.

Examples

Input 1

3
cabcccabc
ccabcc
bcdabc
abcd
aaaxaaaxaaa
axaaaxaa

Output 1

3
3
10

Input 2

4
aaaaaaaaa
a
abacab
caba
baaabaab
aabaaab
bbabbbabb
bbbabbb

Output 2

45
4
2
3