说明

假设爸爸对应的基因序列为$X={x_1，x_2，x_3，…，x_m}$，孩子对应的基因序列$Y={y_1，y_2，y_3，…，y_n}$，那么怎么找到他们有多少相似的基因呢？

如果按照严格递增的顺序，从爸爸的基因序列X中取出一些值，组成序列$Z={x_{i1}，x_{i2}，x_{i3}，…，x_{ik}}$，其中下标${i_1，i_2，i_3，…，i_k }$是一个严格递增的序列。那么就说Z是X的子序列，$Z$中元素的个数就是该子序列的长度。

$X$和$Y$的公共子序列是指该序列既是$X$的子序列，也是$Y$的子序列。

最长公共子序列问题是指：给定两个序列$X={x_1，x_2，x_3，…，x_m}和Y={y_1，y_2，y_3，…，y_n}$，找出$X$和$Y$的一个最长的公共子序列。

输入格式

第一行是一个整型数m(m<100)表示共有m组测试数据。

每组测试数据的第一行是一个字符串s1(0<字符串长度<1000)。

第2行，是一个字符串s2(0<字符串长度<1000)。

输出格式

对于每一组输入，输出s1和s2的最长公共子序列长度。

每组的输出占一行。

样例

2
ABCADAB
BACDBA
ACDEF
ADF

4
3

来源

《趣学算法》4.3节