Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
114 - ZOJ 10th Anniversary Contest - G
Marlon's String

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Long long ago, there was a coder named Marlon. One day he picked two string on the street. A problem suddenly crash his brain...

Let Si..j denote the i-th character to the j-th character of string S.

Given two strings S and T. Return the amount of tetrad (a,b,c,d) which satisfy Sa..b + Sc..d = T , ab and cd.

The operator + means concate the two strings into one.

Input

The first line of the data is an integer Tc. Following Tc test cases, each contains two line. The first line is S. The second line is T. The length of S and T are both in range [1,100000]. There are only letters in string S and T.

Output

For each test cases, output a line for the result.

Sample Input

1
aaabbb
ab

Sample Output

9

Author: CHEN, Weijie
Submit    Status