Problem:

输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。
我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。
需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可

Solution:

题中需要求的是a和b合并之后的最大回文子串是多长。
我们假设当前有一个字符串c，他是由a中的la到ra之间的字符串和b中的lb和rb之间的字符串组成，那么对于c来说，组成回文串有以下可能
（1）a(la+1,ra-1) + b(lb,rb) 是回文串，并且a[la] == a[ra]
（2）a(la,ra) + b(lb + 1,rb - 1) 是回文串，并且b[lb] == b[rb]
（3）a(la + 1,ra) + b(lb,rb - 1) 是回文串，并且a[la] == b[rb]
（4）a(la,ra - 1) + b(lb + 1,rb) 是回文串，并且a[ra] == b[lb]
因此，我们就找出了状态方程dp[la][ra][lb][rb],表示的是a(la,ra) + b(lb,rb)能否组成回文串
我们需要找到方程的储实状态，这里的初始状态即为1个字符的时候，因为它一定是回文串，因此我们需要从初始状态开始往后求解答案，
所以我们可以首先遍历a和b的长度（从0-len），然后在遍历他们的起点la，lb
当ra - la + 1 + rb - lb + 1 <= 1时， dp[la][ra][lb][rb]=1
否则 dp[la][ra][lb][rb] |= （1）|（2）|（3）|（4） 

// https://ac.nowcoder.com/acm/problem/13230
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define _for(i,s,t) for(int i=s;i<t;i++)
#define _rof(i,s,t) for(int i=s;i>t;i--)
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define per(i,s,t) for(int i=s;i>=t;i--)
#define Ri(x) scanf("%d",&x)
#define Rii(x,y) scanf("%d%d",&x,&y)
#define INF 0x3f3f3f3f
using namespace std;
template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
typedef long long ll;
const int maxn = 50 + 10;
bool dp[maxn][maxn][maxn][maxn];
string A,B;
int ans;
int main(){
    IOS;
    int T;
    cin>>T;
    while(T--){
        cin>>A>>B;
        ans = 1;
        int lena = A.length(),lenb = B.length();
        rep(len_a,0,lena) rep(len_b,0,lenb){
            for(int la = 1;len_a + la - 1 <= lena;la ++) for(int lb = 1;len_b + lb - 1 <= lenb;lb ++){
                int ra = len_a + la - 1;
                int rb = len_b + lb - 1;
                if(len_a + len_b <= 1){
                    dp[la][ra][lb][rb] = 1;
                }else{
                    dp[la][ra][lb][rb] = 0;
                    dp[la][ra][lb][rb] |= (dp[la + 1][ra - 1][lb][rb] && A[la - 1] == A[ra - 1]);
                    dp[la][ra][lb][rb] |= (dp[la + 1][ra][lb][rb - 1] && A[la - 1] == B[rb - 1]);
                    dp[la][ra][lb][rb] |= (dp[la][ra - 1][lb + 1][rb] && A[ra - 1] == B[lb - 1]);
                    dp[la][ra][lb][rb] |= (dp[la][ra][lb + 1][rb - 1] && B[lb - 1] == B[rb - 1]);
                }
                if(dp[la][ra][lb][rb]){
                    ans = max(ans,ra - la + 1 + rb - lb + 1);
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
/**
Problem:
输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。
我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。
需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可

Solution: 
题中需要求的是a和b合并之后的最大回文子串是多长。
我们假设当前有一个字符串c，他是由a中的la到ra之间的字符串和b中的lb和rb之间的字符串组成，那么对于c来说，组成回文串有以下可能 
（1）a(la+1,ra-1) + b(lb,rb) 是回文串，并且a[la] == a[ra]
（2）a(la,ra) + b(lb + 1,rb - 1) 是回文串，并且b[lb] == b[rb] 
（3）a(la + 1,ra) + b(lb,rb - 1) 是回文串，并且a[la] == b[rb]
（4）a(la,ra - 1) + b(lb + 1,rb) 是回文串，并且a[ra] == b[lb]
因此，我们就找出了状态方程dp[la][ra][lb][rb],表示的是a(la,ra) + b(lb,rb)能否组成回文串
我们需要找到方程的储实状态，这里的初始状态即为1个字符的时候，因为它一定是回文串，因此我们需要从初始状态开始往后求解答案，
所以我们可以首先遍历a和b的长度（从0-len），然后在遍历他们的起点la，lb
当ra - la + 1 + rb - lb + 1 <= 1时， dp[la][ra][lb][rb]=1
否则 dp[la][ra][lb][rb] |= （1）|（2）|（3）|（4） 
*/