Longest Palindromic Subsequence from Two Strings

In this problem, you are given two strings A and B. Your task is to compute the length of the longest palindromic string that can be formed by selecting a subsequence from A and a subsequence from B. In other words, you need to find a string S which is a subsequence of A and whose reverse is a subsequence of B. The answer is the length of S. The solution uses dynamic programming with the following recurrence:

[ \text{dp}[i][j] = \begin{cases} \text{dp}[i-1][j-1]+1 & \text{if } A[i-1] = B_{rev}[j-1]
\max(\text{dp}[i-1][j],, \text{dp}[i][j-1]) & \text{otherwise} \end{cases} ]

where (B_{rev}) is the reverse of B. This dynamic programming approach is essentially equivalent to computing the longest common subsequence (LCS) between A and (B_{rev}).

You must implement a program that reads the input from standard input (stdin) and prints the output to standard output (stdout).

inputFormat

The first line of the input contains a single integer T, the number of test cases.

Each test case consists of two lines, where the first line contains the string A and the second line contains the string B.

It is guaranteed that both A and B consist only of lowercase English letters.

outputFormat

For each test case, output a single line containing one integer — the length of the longest palindromic string that can be formed as described.

## sample

2
abc
cba
xy
yx

3
2

</p>