Question
Minimize the LCS Power
In a world of enchanted texts, Riya is given a magical task by a wise sage. She receives two strings, A and B, both of length N, filled with mystical lowercase English letters. Her quest is to minimize the power of their Longest Common Subsequence (LCS), which represents the shared magical bond between the two strings. However, Riya has the freedom to rearrange the letters in both strings in any way she wishes to weaken this bond.
Help Riya discover the minimum possible length of the LCS between the two strings, once she rearranges them optimally to break the shared power.
Help Riya discover the minimum possible length of the LCS between the two strings, once she rearranges them optimally to break the shared power.
Input
The first line of the input contains a single integer T, denoting the number of test cases.
Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N - denoting the length of A and B.
- The second line of each test case contains a string A.
- The third line of each test case contains a string B.
Constraints
1 ≤ T ≤ 1000
1 ≤ N ≤ 105
A and B contains lower case english letters.
The sum of N over all test cases dose not exceed 2.105
Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N - denoting the length of A and B.
- The second line of each test case contains a string A.
- The third line of each test case contains a string B.
Constraints
1 ≤ T ≤ 1000
1 ≤ N ≤ 105
A and B contains lower case english letters.
The sum of N over all test cases dose not exceed 2.105
Output
For each test case, output the minimum length of LCS Riya can obtain.
Example
Sample Input
2
4
aaaa
aaab
1
c
z
Sample Output
3
0
Explanation
Test case 1: LCS(aaaa, aaab) = aaa. It can be shown that no other rearrangement of the strings produces a smaller LCS.
2
4
aaaa
aaab
1
c
z
Sample Output
3
0
Explanation
Test case 1: LCS(aaaa, aaab) = aaa. It can be shown that no other rearrangement of the strings produces a smaller LCS.