Cho hai xâu \(S\) và \(T\) chỉ gồm các ký tự in thường 'a' đến 'z'. Tìm độ dài xâu con chung không liền kề dài nhất (subsequence) của hai xâu \(S\) và \(T\).

Input

• Dòng thứ nhất chứa số nguyên dương duy nhất là số bộ test \(T\) \((T \leq 40)\).
• Mỗi test gồm \(2\) dòng, mỗi dòng chứa một xâu gồm các kí tự trong 'a' đến 'z' viết liền nhau, giới hạn độ dài không quá \(10^3\).

Output

• Ghi ra \(T\) dòng, mỗi dòng là kết quả tương ứng cho một test là độ dài xâu con chung không liền kề dài nhất.

Example

1
abc
ab 

1