Cho 2 chuỗi s1 và s2, tìm độ dài chuỗi con chung dài nhất (chuỗi con dài nhất có cả trong 2 chuỗi đã cho).

Input

• Dòng đầu tiên là số bộ test \(t\).
• \(2 \times t\) dòng tiếp theo mô tả \(t\) bộ test, mỗi bộ test gồm 2 chuỗi nằm trên 2 dòng riêng biệt.

Output

• Với mỗi bộ test, output độ dài chuỗi con chung dài nhất trên 1 dòng riêng biệt.

Constraints

• \(1 \le t \le 10^3\)
• Chuỗi s1 và s2 có độ dài không quá \(10^3\) ký tự.

Example

Sample input

2
AGGTAB
GXTXAYB
BD
ABCD

Sample output

4
2