Ta gọi xâu \(R\) là xâu con của xâu \(S\) nếu ta có thể thu được xâu \(R\) bằng cách xóa đi một vài ký tự của xâu \(S\) và giữ nguyên thứ tự các ký tự còn lại.

Xâu ký tự \(C\) được gọi là xâu con chung của hai xâu \(A\) và \(B\) nếu \(C\) là xâu con của \(A\) và \(C\) là xâu con của \(B\). Trong bài tập này nhiệm vụ của bạn như sau: Bạn được cho \(3\) chuỗi \(X,Y,Z\) nhiệm vụ là tìm chuỗi con chung dài nhất trong cả ba chuỗi đã cho.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(T\) biểu thị số lượng trường hợp kiểm tra. \((1 \le T \le 30)\)
• Sau đó \(T\) trường hợp: Dòng đầu tiên của mỗi trường hợp thử nghiệm chứa các số nguyên \(n,m,k\) lần lượt biểu thị độ dài của chuỗi \(X,Y,Z\) \((1 \le n,m,k \le 100)\)
• Dòng thứ hai của mỗi trường hợp kiểm tra chứa ba chuỗi \(X,Y,Z\). Chuỗi chỉ bao gồm các bảng chữ cái tiếng Anh viết thường.

Dữ liệu ra

• In độ dài của chuỗi con chung dài nhất trong ba chuỗi cho mỗi trường hợp thử nghiệm trong một dòng mới.

Input 1

2
5 5 5
aaabb bbaaa cccbb
7 6 5
abcd1e2 bc12ea bd1ea

Output 1

2
3