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

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

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

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

输入格式

第一行一个整数 TTT

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

输出格式

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

样例

样例输入

2
aa
bb
a
aaaabcaa

样例输出

4
5

数据范围与提示

T≤50 T \leq 50T50
∣a∣,∣b∣≤50|a|,|b| \leq 50a,b50