题目描述

输入两个串 $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$ 的价值。

样例

输入

2
ACGT
ACGT
AACCGGTT
ACACAGAT

输出

4
7

数据范围与提示

$T \leq 500$

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

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