题目描述

输入两个串 $a,b$ ，你需要把 $a,b$ 组合成一个串 $c$ ，使得 $|c|=|a|+|b|$ 且 $c$ 可以拆成两个没有重复元素的子序列的并，使得一个子序列为 $a$ ，另一个子序列为 $b$ 。 一个字符串 $s$ 的价值定义如下（ $n=|s|>1$ ）：

枚举所有的分界线 $1 \leq k \leq n-1$，令$u=s{[1,k]},v=s{[k+1,n]}$ ，将 $u,v$ 的字符重新排列使得 $u,v$ 的最长公共前缀最大，所有可能的分界线中 $u,v$ 的最长公共前缀的最大值就是这个字符串的价值。

例如字符串 $\texttt{ACGTTTGCAT}$ 的价值为 $5$ ，因为均分成两半之后得到 $u=\texttt{ACGTT},v=\texttt{TGCAT}$ ，重新排列之后可以做到 $u=v$ 即最长公共前缀为 $5$ 。

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

输入格式

第一行一个整数 $T$ 。

接下来 $2T$ 行，每两行两个字符串分别代表 $a,b$ 。

输出格式

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

样例

input

2
ACGT
ACGT
AACCGGTT
ACACAGAT

output

4
7

数据范围与提示

$T \leq 500$

$|a|,|b| \leq 100,000;\sum |a|+|b| \leq 500,000$

$a,b$ 的字符集为 ${\texttt{A,C,G,T}}$