MAIN8_E - Cover the string

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

Added by:Mahesh Chandra Sharma
Date:2011-04-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for NSIT-IIITA Main contest #8

hide comments
2011-04-24 10:53:48 sandeep pandey
is it possible to accept d O[N^2] solution??


NO

Last edit: 2013-01-31 17:01:55
2011-04-24 04:19:49 Azamat Ahmedov
Max(T)=?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.