Cho một xâu S, gọi hàm F(S) là số phần nhỏ nhất chứa các ký tự liên tiếp giống nhau trong S. Hay nói cách khác, F(S) bằng 1 lượng cộng với số lượng chỉ số i sao cho ~S_i~ ≠ ~S_{i+1}~.

Bạn được cho hai xâu A và B với độ dài lần lượt là N và M. Bạn cần trộn hai xâu này thành một xâu C với độ dài N+M. Đặc biệt, mỗi ký tự của C thuộc A hoặc B, tất cả các ký tự trong A phải có thứ tự giống với thứ tự ở trong C và tất cả các ký tự trong B phải có thứ tự giống với thứ tự của chúng ở trong B.

Tính giá trị nhỏ nhất có thể của F(C).

Dữ liệu vào

• Dòng đầu tiên chứa một số nuyên T thể hiện số test. Các test được miêu tả như sau.
• Dòng đầu tiên của mỗi test chứa hai số nguyên N và M.
• Dòng thứ hai chứa một xâu A với độ dài N.
• Dòng thứ ba chứa một xâu B với độ dài M.

Dữ liệu ra

Với mỗi test, in ra một dòng chứa một số nguyên là giá trị nhỏ nhất có thể của F(C).

Ràng buộc

• 1 ≤ T ≤ 100
• 1 ≤ N, M ≤ 5000
• 1 ≤ Tổng của N trong tất cả các test ≤ 5000
• 1 ≤ Tổng của M trong tất cả các test ≤ 5000
• Xâu A, B chỉ chứa các chữ cái tiếng Anh in thường.

Subtasks

• Subtask 1 (1 điểm): 1 ≤ T, N, M ≤ 10
• Subtask 2 (1 điểm): Các ký tự trong A và B được sắp xếp theo thứ tự không giảm.
• Subtask 3 (1): Ràng buộc gốc.

Ví dụ

Input:

1 
4 4 
abab baba

Output:

5

Giải thích

Ví dụ: Xâu C phù hợp với đáp án là "abbaabba".