题目描述

给定 $2$ 个字符串 $s_1$ 和 $s_2$ ，如果 $s_2$ 中所有的字符，在 $s_1$ 中都存在，且在 $s_1$ 中的下标顺序是严格递增的，那么我们将 $s2$ 称之为 $s1$ 的子序列。

比如：

$s_1 = "abcdef"$ ， $s_2 = "bdf"$ ，则 $s_2$ 按上述条件是 $s_1$ 的子序列。

现给你两个字符串 $s_1$ 和 $s_2$ ，请问它们的最长公共子序列的长度是多少？

输入

输入包含多组测试数据，第 $1$ 行有一个整数 $n$ 表示测试数据的组数（不超过 $100$ 组）。

接下来 $n$ 行，每行为两个仅包含小写字母的字符串，由 $1$ 个空格分隔。每个字符串的长度不超过 $100$ 。

输出

对于每组输入，输出两个字符串的最长公共子序列的长度。

样例

3
abcfbc abfcab
programming contest 
abcd mnp

4
2
0