#P1295C. Obtain The String
Obtain The String
No submission language available for this problem.
Description
You are given two strings and consisting of lowercase Latin letters. Also you have a string which is initially empty. You want string to be equal to string . You can perform the following operation to achieve this: append any subsequence of at the end of string . A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, if , , you may turn into following strings in one operation:
- (if we choose subsequence );
- (if we choose subsequence );
- (if we choose subsequence ).
Note that after this operation string doesn't change.
Calculate the minimum number of such operations to turn string into string .
The first line contains the integer () — the number of test cases.
The first line of each testcase contains one string () consisting of lowercase Latin letters.
The second line of each testcase contains one string () consisting of lowercase Latin letters.
It is guaranteed that the total length of all strings and in the input does not exceed .
For each testcase, print one integer — the minimum number of operations to turn string into string . If it's impossible print .
Input
The first line contains the integer () — the number of test cases.
The first line of each testcase contains one string () consisting of lowercase Latin letters.
The second line of each testcase contains one string () consisting of lowercase Latin letters.
It is guaranteed that the total length of all strings and in the input does not exceed .
Output
For each testcase, print one integer — the minimum number of operations to turn string into string . If it's impossible print .