Given two strings A and B. You have to find the length of the smallest substring of A, such that B is the subsequence of this substring.

Formally speaking you have to find the length of smallest possible string S such that:

• S is the substring of A.
• B is the subsequence S.

Note: Subsequence of an string S is obtained by deleting some (possibly none) of the characters from it. for example "ah" is the subsequence of "aohol".

Input

First line contains T, the number of test cases. Then T test cases follow, 2 lines for each test case, 1st contains A and 2nd contain B.

|A| ≤ 20000, |B| ≤ 100

Output

For each test case print the answer in a new line. if no such substring exists print -1 instead.

Example

Input:
2
aaddddcckhssdd
acs
ghkkhllhjkhthkjjht
hh
Output:
10
3