Clara 有两个字符串 $s$ 和 $t$。她想要从 $s$ 中选出一个子序列 $x$，从 $t$ 中选出一个子序列 $y$，使得：

• $x$ 在字典序上小于或等于 $y$。
• $|x| + |y|$ 的值最大，其中 $|s|$ 表示字符串 $s$ 的长度。

注意：

• $x$ 和 $y$ 都可以是空字符串。
• 子序列是指从给定序列中删除零个或多个元素，且不改变剩余元素顺序后得到的序列。
• 字符串 $x$ 在字典序上小于字符串 $y$，当且仅当 $x$ 是 $y$ 的前缀（且 $x \neq y$），或者存在某个 $i$ ($1 \le i \le \min(|x|, |y|)$)，使得 $x_i < y_i$，且对于所有 $j$ ($1 \le j < i$)，满足 $x_j = y_j$。

输入包含多组测试数据，以文件结束符（EOF）终止。对于每组测试数据： 第一行包含一个字符串 $s$。第二行包含一个字符串 $t$。

• $1 \le |s| \le 2000$
• $1 \le |t| \le 2000$
• $|s|$ 的总和不超过 $20000$。
• $|t|$ 的总和不超过 $20000$。
• 两个字符串均仅由小写英文字母组成。

对于每组测试数据，输出 $|x| + |y|$ 的最大值。

样例

输入格式 1

aaaa
bbbb
abcd
abca
abcd
abcd

输出格式 1

8
7
8