题目描述

这里有两个可以显示大写字母序列的显示屏。初始时，两个屏幕都没有显示任何东西。

每秒钟你可以执行下列两种操作中的一种：

• 选择一个屏幕和一个大写字母，并将该字母添加到该屏幕上显示的序列的末尾；
• 选择一个屏幕并将该屏幕上的序列复制到另一个屏幕，覆盖另一个屏幕上显示的序列。

你需要计算让第一个屏幕显示序列 $s$，第二个屏幕显示序列 $t$ 所需要花费的最少秒数。

输入格式

本题有多组测试数据。

第一行有一个整数 $q$，表示数据组数。

每组测试数据由两行组成。第一行有一个字符串 $s$，第二行有一个字符串 $t$。两个字符串均由大写字母组成。

输出格式

对于每组测试数据，输出一行一个整数，表示需要花费的最少秒数。

说明/提示

【样例解释】

对于第一组数据，以下是一种可能的操作方案：

• 花费 6 秒向第一个屏幕写入序列 GARAGE；
• 花费 1 秒将序列从第一个屏幕复制到第二个屏幕；
• 花费 7 秒向第二个屏幕写入序列 FORSALE。

对于第二组数据，以下是一种可能的操作方案：

• 花费 1 秒向第二个屏幕写入序列 A；
• 花费 1 秒将序列从第二个屏幕复制到第一个屏幕；
• 花费 4 秒向第一个屏幕写入序列 BCDE；
• 花费 4 秒向第二个屏幕写入序列 ABCD。

对于第三组数据，最快的方法是将字母一个一个地写入屏幕，而不进行复制，这需要花费 16 秒。

对于所有测试数据，保证 $1 \le q \le 500$，$1 \le |s|,|t| \le 100$。

翻译来自 Jason_Ming。

样例

3
GARAGE
GARAGEFORSALE
ABCDE
AABCD
TRAINING
DRAINING

14
10
16