시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3 3 3 100.000%

문제

How many distinct strings can be obtained by concatenating a non-empty suffix of string a with a non-empty prefix of string b?

입력

The first line contains a single integer t (1 ≤ t ≤ 105), denoting the number of test cases.

Each test case is described with strings a and b on separate lines. Both strings consist of lowercase English letters and have length between 1 and 105, inclusive.

The total length of strings over all test cases does not exceed 2 · 105.

출력

For each test case, display the required number.

예제 입력 1

5
abb
bba
aaa
aaaaa
winter
camp
ehehe
heheh
aaaaaaabaaaa
aabaaaaaa

예제 출력 1

8
7
24
16
97

힌트

In the first test case, all obtainable strings are abbb, abbbb, abbbba, bb, bbb, bbba, bbbb, bbbba.

In the second test case, only strings consisting of at least 2 and at most 8 letters a can be obtained.