一位教授怀疑某位学生的论文是从某本书中抄袭的。为了验证这一点，他想要计算该论文与这本书的最长公共子序列。他没有现成的程序来完成这项工作，因此他请你编写一个程序，作为算法课程的作业。
输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 10^9$)。接下来是各测试用例的描述。
每个测试用例由两行组成。第一行包含一个长度在 $1$ 到 $1\,000\,000$ 之间、由小写拉丁字母组成的字符串：书的内容。第二行包含一个长度在 $1$ 到 $1000$ 之间、由小写拉丁字母组成的字符串：论文的内容。
所有测试用例中书的长度之和最多为 $10\,000\,000$。所有测试用例中论文的长度之和最多为 $30\,000$。
对于每个测试用例，输出书和论文的最长公共子序列的长度。
1 abcdefghijklmnopqrstuvwxyz bbddee
3
The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.
This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.
If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.
Guidelines: