题目描述

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

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

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

输入格式

第一行一个整数 $T$。

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

输出格式

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

样例

input

2
aa
bb
a
aaaabcaa

output

4
5

数据范围与提示

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