Given two strings s1 and s2, find the length of their longest common subsequence (LCS). If there is no common subsequence, return 0.

The strings are composed of lower case English alphabets.

A subsequence of a string is a string that can be derived by deleting some or no characters such that the order of the remaining characters remain the same.

Example

s1: "workattech"
s2: "branch"
Result: 4
Explanation: Longest common subsequence is "rach"

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.
For each test case, the input has two lines:

• The string s1.
• The string s2.

Output Format

For each test case, the output contains a line with one integer denoting the length of the longest common subsequence.

Sample Input

4
workattech
branch
helloworld
playword
hello
hello
abc
def

Expected Output

4
5
5
0

Constraints

1 <= T <= 10
1 <= s1.length, s2.length <= 3000