最长公共子序列（Longest Common Subsequence，LCS）（不要求连续）。

其定义是：一个序列 S ，分别是两个已知序列的子序列，且所有符合此条件序列中最长的，则 S 为已知序列的最长公共子序列。

【输入描述】

输入一行，包含两个序列 a 和 b，保证序列长度不超过 200 。

【输出描述】

输出最长公共子序列的长度。

【输入样例】

123abc abc123abc

【输出样例】

6

【参考程序】

// 爱码岛编程
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 210;
int dp[MAXN][MAXN];
char s1[MAXN], s2[MAXN];

int main() {
    int T;
    cin >> T;
    while (T--) {
        memset(dp, 0, sizeof(dp));
        cin >> s1 + 1;
        cin >> s2 + 1;
        int m, n;
        m = strlen(s1 + 1);
        n = strlen(s2 + 1);
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1[i] == s2[j]) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        cout << dp[m][n] << endl;
    }
    return 0;
}