#6163. 「美团 CodeM 初赛 Round A」合并回文子串

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

输入两个串 a,b ,你需要把 a,b 组合成一个串 c ,使得 |c|=|a|+|b| c 可以拆成两个没有重复元素的子序列的并,使得一个子序列为 a ,另一个子序列为 b

一个字符串的价值定义为其最长回文子串的长度。

你需要求出所有可能的 c 中价值最大的字符串,输出这个最大价值即可。

输入格式

第一行一个整数 T

接下来 2T 行,每两行两个字符串分别代表 a,b a,b 的字符集为全体小写字母。

输出格式

对于每组数据,输出一行一个整数表示价值最大的 c 的价值。

样例

样例输入

2
aa
bb
a
aaaabcaa

样例输出

4
5

数据范围与提示

T \leq 50
|a|,|b| \leq 50