Description

给定两个字符串A和B, 请计算这两人个字符串的最长公共子序列长度。

Input

第一行输入M(M<=10)表示有M组数据。每组数据输入两行字符串, 字符串的长度不长于500。

Output

输出M行正整数，第i行表示第i组数据的最长公共子序列长度。

Sample Input

2
abcdefg
cemg
abcdefgh
ceaaegh

Sample Output

3
4