Obtain The String

You are given two strings s and t consisting of lowercase Latin letters. Also you have a string z which is initially empty. You want string z to be equal to string t. You can perform the following operation to achieve this: append any subsequence of s at the end of string z. 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 z = ac, s = abcde, you may turn z into following strings in one operation:

1. z = acace (if we choose subsequence ace);
2. z = acbcd (if we choose subsequence bcd);
3. z = acbce (if we choose subsequence bce).

Note that after this operation string s doesn't change.

Calculate the minimum number of such operations to turn string z into string t.

Input

The first line contains the integer T (1 ≤ T ≤ 100) — the number of test cases.

The first line of each testcase contains one string s (1 ≤ |s| ≤ 10^5) consisting of lowercase Latin letters.

The second line of each testcase contains one string t (1 ≤ |t| ≤ 10^5) consisting of lowercase Latin letters.

It is guaranteed that the total length of all strings s and t in the input does not exceed 2 ⋅ 10^5.

Output

For each testcase, print one integer — the minimum number of operations to turn string z into string t. If it's impossible print -1.

Example

Input

3 aabce ace abacaba aax ty yyt

Output

1 -1 3

inputFormat

Input

The first line contains the integer T (1 ≤ T ≤ 100) — the number of test cases.

The first line of each testcase contains one string s (1 ≤ |s| ≤ 10^5) consisting of lowercase Latin letters.

The second line of each testcase contains one string t (1 ≤ |t| ≤ 10^5) consisting of lowercase Latin letters.

It is guaranteed that the total length of all strings s and t in the input does not exceed 2 ⋅ 10^5.

outputFormat

Output

For each testcase, print one integer — the minimum number of operations to turn string z into string t. If it's impossible print -1.

Example

Input

3 aabce ace abacaba aax ty yyt

Output

1 -1 3

样例

3
aabce
ace
abacaba
aax
ty
yyt

1
-1
3

</p>