题目描述
输入两个串 $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|\leq50$