You are given two strings 'str1' and 'str2'. Find the minimum operations required to convert str1 into str2.
An Operation is defined as:
A character from an index of a string(str1) is put at the end of it, is defined as a single operation.
You cannot perform any operation on the string, str2.
Input format :
The first line of input contains a single integer 'T' denoting the number of test cases or queries to be run.
The first line of each test case contains a string, representing str1.
The second line of each test case contains a string, representing str2.
Output Format :
For each test case/query, print the minimum number of operations required to convert str1 into str2. Print -1 if it is not possible.
Output for every test case will be printed in a separate line.
You are not required to print the output explicitly, it has already been taken care of. Just implement the function.
Input strings contain only lower case and uppercase letters and do not contain blank spaces.
1 <= T <= 10
1 <= N <= 10^5
1 <= M <= 10^5
Where N and M are the lengths of the input strings 'str1', and 'str2' respectively.
Time Limit: 1 sec
Sample Input 1 :
Sample Output 1 :
Explanation of Sample Input 1:
For the first test case, we can move 'B' to the end of str1 so str1 becomes 'ACB' which is equal to the str2. Hence 1 operation was needed.
For the second test case, move 'A' to the end of str1 so new string becomes 'bcDA', Now move 'D' to the end so we have now str1 = 'bcAD' which is equal to the str2. Hence 2 operations were needed.
Sample Input 2 :
Sample Output 2 :