给定两个字符串 $s$ 和 $t$，其中 $s$ 是一个仅包含小写字母的字符串，$t$ 是一个包含小写字母和大写字母的模式串。

定义一个字符串可以被一个模式串匹配：

• 模式串中的一个小写字母匹配一个对应的小写字母。
• 模式串中的一个大写字母匹配任意数量（包括零个）对应的小写字母。

例如，abb 可以被 aB 匹配；aaa 可以被 A 匹配；ac 可以被 aBc 匹配；而 ABC、aABCc、aab 不能被 aB 匹配；aa 不能被 a 匹配。

现在你需要求出 $s$ 的最长子串的长度，使得该子串可以被 $t$ 匹配。

输入格式

本题包含多组测试数据。

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试数据的组数。

对于每组测试数据，第一行包含一个字符串 $s$ ($1 \le |s| \le 10^5$)，第二行包含一个字符串 $t$ ($1 \le |t| \le 10^5$)。

保证对于所有测试数据，$\sum |s| \le 10^5$，$\sum |t| \le 10^5$，且所有测试数据中 $t$ 的大写字母总数不超过 $200$。

输出格式

对于每组测试数据，在一行中输出可以被 $t$ 匹配的 $s$ 的最长子串的长度。

样例

输入样例 1

3
aaa
ABa
aaa
aAaBa
aaa
aa

输出样例 1

3
3
2