Shortest Common Supersequence Length

This problem requires you to compute the length of the shortest common supersequence of two given strings A and B. A supersequence of two strings is a string that contains both as subsequences. It can be shown that the length of the shortest common supersequence is given by the formula:

\( |A| + |B| - \text{LCS}(A, B) \)

where \( \text{LCS}(A, B) \) is the length of the longest common subsequence of A and B. Your task is to implement an algorithm to compute this value for multiple test cases.

Note: Each test case provides an integer N that represents the length of string A, though it is not used directly in the computation.

inputFormat

The input begins with an integer T on the first line, representing the number of test cases. Each of the following T lines contains a test case with three items separated by spaces:

• An integer N (the length of string A, not used in the calculation).
• A string A.
• A string B.

Read the input from stdin.

outputFormat

For each test case, output a single integer on a new line denoting the length of the shortest common supersequence of A and B. Output the result to stdout.

The result is computed using the formula: \( |A| + |B| - \text{LCS}(A, B) \).

## sample

5
4 abac cab
3 abc abc
2 ab bc
6 abcdef defabc
1 a b

5
3
3
9
2

</p>