C++ or Java

Palindromic String Problem

You are given two strings S1 and S2. You need to convert the string S1 into a palindromic string such that it contains the string S2 as its substring by using minimum number of operations. You are allowed to use only one type of operation i.e., you can replace any character of the string S1 with any other character.

Input format

First line: TEST denoting the number of test cases

For each test case,

First line: String S1

Second line: String S2

Note

Both the strings can contain lower and upper case letters only.

The upper case letter and its corresponding lower case letter are not the same. For example, A and a are considered as distinct characters.

Output format

Print the minimum number of operations that are required in a single line. If that is not possible, print 1.

Constraints

1TEST5

1 Length (S1,S2)5000

Sample Input

2 archit ar aaaaa bbb 

Sample Output

3 3 

Explanation

In the first sample, we can get a string "arccra" or " arhhra" as our final string which is both palindromic as well as contains "ar" as substring. We can see that our final string differs from original string i.e. "archit" in exactly 3 places. So, minimum number of operations required is 3.

Note: Your code should be able to convert the sample input into the sample output. However, this is not enough to pass the challenge, because the code will be run on multiple test cases. Therefore, your code must solve this problem statement.