Maior Subsequência Comum X47150

Dada duas sequências de caracteres, imprima o comprimento da maior subsequência comum entre as duas sequências. Por exemplo, a maior subsequência entre as sequências ’abcddgh’ e ’aedfhr’ é ’adh’ de comprimento 3.

Input

A entrada consiste em pares de linhas. A primeira linha de um par contém a primeira string e a segunda linha contém a segunda string. Cada string é uma sequência de no máximo 1.000 caracteres.

Output

Para cada par presente na entrada, imprima um inteiro correspondente ao comprimento da maior subsequência comum entre as duas strings.