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