You are given two strings 'A' and 'B' where string 'A' is fixed. But you can perform left shift operations on string B any number of times.

Your task is to find out the minimum number of left-shift operations required in order to obtain the longest common prefix of string 'A' and 'B'.

Note:

Left shift is defined as a single circular rotation on the string after which the first character becomes the last character and all other characters are shifted one index to the left.

For Example:

If A = “an”, B = “can”.
After performing one left shift operation, string B becomes “anc”.
After performing two left shift operations, string B becomes “nca”.

Follow Up:

Can you solve this in linear time and space complexity?

Input format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. 
Then, the T test cases follow.

The first line of each test case contains the string A.

The second line of each test case contains the string B.

Output format:

For each test case, print the minimum number of left shift operations required in order to obtain the longest common prefix of string A and B.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= |A|, |B| <= 5 * 10^4
Where |A| and |B| denote the length of string, A and B respectively.   

All the characters of the string A and B contain lowercase English letters only.

Time limit: 1 second