Ben was playing with the Omnitrix in free time. He screwed up once again. Not knowing what he was doing, he accessed the DNA analysis and  modification subroutine of the watch and accidentally manipulated the  DNA of an alien.
While fighting with Vilgax, he realized that one of his alien is not accessible. He some how  escapes the fight and contacts Azmuth for help. Azmuth isolates the problem easily and he has another sample of the DNA in his lab.
The DNA regeneration device at his lab can re-calibrate the DNA sequence by either adding the missing nucleobases, or by replacing the wrong nucleobase with the right one. The manipulated DNA blueprint in Ben's watch can be of same length as of original or less.
Replacing a corrupt nucleobase need 1 unit of time but simply adding new ones to either end of the DNA does not consume any time.
You only need to find the minimum time in which the DNA regeneration device can re-calibrate the corrupt DNA. 

NOTE: Alien DNA can have more or less than 4 distinctive DNA nucleobases, unlike humans, who have A with T and C with G pairing.
Hence pairing is not to be considered.

INPUT:

First line of input is T, no. of test cases.
Each test case consist of 2 lines,
first line contains the original DNA string followed by next line containing the corrupt DNA string which is to be re-calibrated.

OUTPUT:

For each test case, print the minimum unit of time required to recalibrate the DNA .

CONSTRAINTS
1 ≤ T ≤ 50
1 ≤Length of modified DNA ≤ Length of actual DNA ≤ 1000

SAMPLE INPUT
2
ABCDEFZQT
BPFZQ
ATTCG
ATTCK

SAMPLE OUTPUT
2
1

Explanation

In first case ABCDEFZQT is original DNA and BPFZQ is modified DNA. Here 2 nucleobases are to be replaced, namely B and P.

In second case only K nucleobase is incorrect.
for _ in xrange(input()):
    strB = raw_input();
    strA = raw_input();
    
    l = len(strA);
    minCount = 10000;
    for j in range(0,len(strB)-l+1):
        count = 0;
    
        for i in range(j,l+j):
            if strA[i-j] != strB[i]:
                #print strA[i-j]+" != "+strB[i];
                count += 1;
        #print "Check complete : "+strB[j:l+j];
        if count < minCount:
            minCount = count;
    print minCount