I. Ciallo
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Inaba Meguru, the creator of the viral Ciallo, seeks to expand her linguistic creations by combining prefixes and suffixes from two base words. Formally, she has two strings $$$s$$$ and $$$t$$$, and she will create new strings by concatenating a prefix$$$^{\text{∗}}$$$ of $$$s$$$ and a suffix$$$^{\text{†}}$$$ of $$$t$$$. She wants to know how many different non-empty strings she can obtain in this way.

$$$^{\text{∗}}$$$A string $$$a$$$ is a prefix of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the end. For example, "for" is a prefix of "forever", but "abc" is not a prefix of "aabbc"

$$$^{\text{†}}$$$A string $$$a$$$ is a suffix of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning. For example, "ever" is a suffix of "forever", but "abc" is not a suffix of "aabbc"

Input

Each test contains multiple tests. The first line contains one integer $$$T$$$ ($$$1\le T\le 10^4$$$) — the number of test cases. The description of each test case follows.

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

The second line of each test contains a string $$$t$$$ $$$(1\le |t|\le 10^6)$$$.

It is guaranteed that both $$$s$$$ and $$$t$$$ contain only lower case Latin characters.

It is guaranteed that neither the sum of $$$|s|$$$ nor the sum of $$$|t|$$$ over all test cases exceeds $$$10^6$$$.

Output

For each test case, output an integer indicating the number of different strings Meguru can obtain.

Example
Input
4
a
a
a
b
ciao
hello
inabameguru
ayachinene
Output
2
3
28
122