Cho hai xâu S và T chỉ gồm các chữ cái thường 'a'..'z'. Tìm độ dài xâu con chung dài nhất (subsequence) của hai xâu S và T.

Input

• Dòng đầu tiên chứa duy nhất một số \(T \leq 30\) là số lượng bộ test.
• 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á \(5000\).

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 dài nhất tìm được.

Example

1
wigwwnydtyo
kwmmka

1