String Merging

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
For a string S, let's define a function F(S) as the minimum number of blocks consisting of consecutive identical characters in S. In other words, F(S) is equal to 1 plus the number of valid indices i such that S_{i} ≠ S_{i+1}.
You are given two strings A and B with lengths N and M respectively. You should merge these two strings into one string C with length N+M. Specifically, each character of C should come either from A or B; all characters from A should be in the same relative order in C as in A and all characters from B should be in the same relative order in C as in B.
Compute the minimum possible value of F(C).
Input
 The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
 The first line of each test case contains two spaceseparated integers N and M.
 The second line contains a single string A with length N.
 The third line contains a single string B with length M.
Output
For each test case, print a single line containing one integer — the minimum possible value of F(C).
Constraints
 1 ≤ T ≤ 100
 1 ≤ N, M ≤ 5,000
 1 ≤ sum of N in all test cases ≤ 5,000
 1 ≤ sum of M in all test cases ≤ 5,000
 strings A, B consist only of lowercase English letters
Subtasks
Subtask 1 (10 points): 1 ≤ T, N, M ≤ 10
Subtask 2 (20 points): the characters of A and B are sorted in nondecreasing order
Subtask 3 (70 points): original constraints
Example
Input: 1 4 4 abab baba Output: 5
Explanation
Example case 1: One possible way to choose the string C to get the desired answer is "abbaabba".
Author:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/STRMRG 
Tags  dynamicprogramming, easy, jan18, kingofnumbers, kingofnumbers 
Date Added:  2012018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions