Description

序列的子序列指序列中的一些元素被省略。

给定一个序列$x$$=$$<$$x_1$,$x_2$,…,$x_m$>及另一个序列$z$$=$$<$$z_1$,$z_2$…,$z_k$>，若$x$的索引存在严格递增的序列$<$$i$$1$,$i$$2$,…,$i$$k$>，则对所有$j$$=$$1$,$2$,…,$k$及$x_{ij}$$=$$z_j$，$z$都是$x$的子序列。

例如，$z$$=$$<$$a$,$b$,$f$,$c$>的索引序列是$<$$1$,$2$,$4$,$6$>，它是$x$$=$$<$$a$,$b$,$c$,$f$,$b$,$c$>的子序列。

若$z$既是$x$的子序列，也是$y$的子序列，则称$z$是$x$和$y$的公共子序列。

给定两个序列$x$和$y$，求$x$和$y$的最长公共子序列的长度。

Format

Input

每个测试用例都包含两个表示给定序列的字符串，序列由任意数量的空格分隔。

Output

对每个测试用例，都单行输出最长公共子序列的长度。

Samples

abcfbc abfcab
programming contest
abcd mnp

4
2
0