MAIN8_E  Cover the string
Given two strins A and B. You have to find the length of the smallest substring of A, such that B is the subsequence of this substing.
Formally speaking
you have to find the lenght 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 deletnig some (possibly none) of the characters from it. for example "ah" is the subsequecne 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
hide comments
karthik_kamal:
20130719 10:40:22
my submission gave me wa ans......... Last edit: 20130719 10:41:02 

V0iD!:
20110505 12:05:29
anyone using regex in java to solve this?? any luck at all?? am always getting tle.. :( 

Kashyap Krishnakumar:
20110504 02:28:56
@problem setter: I think the solutions have not been rejudged after change of test cases. So a lot of solutions have passed in lower time. 

Buda IM (retired):
20110429 16:22:57
@Santiago Palacio


Santiago Palacio:
20110428 19:39:57
There is no case where B cannot be made from A right? 

Mahesh Chandra Sharma:
20110426 09:34:13
@ justine. If you are getting TLE then optimize your code. Thats all what I can say ;) 

Mahesh Chandra Sharma:
20110426 09:33:01
I have added a rigorous test case, on which some of the Accepted solutions failed. Please resubmit your solution in case yours failed too. 

Mahesh Chandra Sharma:
20110426 09:30:58
@Azamat T<=20


justine:
20110425 14:10:45
@problem setter:please reply me.( 

justine:
20110424 17:10:05
please tell me why i m getting TLE.

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