Cat

Interview

Time limit2sMemory limit512 MB

Summary

Count how many distinct strings you can form by joining a non-empty suffix of a with a non-empty prefix of b.

Level: Medium6 of 10
Topics: String, String matching, Math, Hash map
Solved: No attempts yet

Problem

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

Input

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.

Output

For each test case, display the required number.

Hint

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.

Examples1

Example 1

Input

5
abb
bba
aaa
aaaaa
winter
camp
ehehe
heheh
aaaaaaabaaaa
aabaaaaaa

Expected output