Prefixo

Em programas de computador, palavras, como “otorrinolaringologista” ou “escolaridade”, são normalmente representadas por uma cadeia de caracteres. Um prefixo de uma palavra é qualquer sequência de caracteres consecutivos que se inicia no primeiro caractere da palavra. Por exemplo, “escola” e “esco” são prefixos de “escola”, mas “cola” não é.

Um prefixo comum de duas palavras é uma cadeia de caracteres que é prefixo das duas palavras. Por exemplo, “a”, “aba” e “abaca” são exemplos de prefixos comuns das palavras “abacate” e “abacaxi”.

Dadas duas palavras, escreva um programa para calcular o comprimento do maior prefixo comum, em número de caracteres.

Entrada

A primeira linha de entrada contém um inteiro $N$, o número de caracteres da primeira palavra. A segunda linha contém uma cadeia com $N$ caracteres $P_i$, a primeira palavra. A terceira linha contém um inteiro $M$, o número de caracteres da segunda palavra. A quarta linha contém uma cadeia com $M$ caracteres $S_i$, a segunda palavra.

Saída

Seu programa deve produzir uma única linha, contendo um único inteiro, o número de caracteres do maior prefixo que é comum às duas sequências.

Restrições

• $1 \leq N \leq 1\ 000$
• $1 \leq M \leq 1\ 000$
• As palavras contêm apenas letras minúsculas sem acentuação.

Informações sobre a pontuação

A tarefa vale $100$ pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima:

• Subtarefa 1 (33 pontos): $N = M$
• Subtarefa 2 (67 pontos): Nenhuma restrição adicional.

Seu programa pode resolver corretamente todas ou algumas das subtarefas (elas não precisam ser resolvidas em ordem). Sua pontuação final na tarefa é a soma dos pontos de todas as subtarefas resolvidas corretamente por alguma das suas submissões.

Exemplos

Exemplo de entrada 1

7
abacate
7
abacaxi

Exemplo de saída 1

5

Explicação do exemplo 1: “abaca”, com 5 caracteres, é o maior prefixo comum entre “abacate” e “abacaxi”, portanto 5 é a resposta.

Exemplo de entrada 2

8
paralelo
13
paralelogramo

Exemplo de saída 2

8

Explicação do exemplo 2: “paralelo”, com 8 caracteres, é o maior prefixo comum entre “paralelo” e “paralelogramo”, portanto 8 é a resposta.

Exemplo de entrada 3

6
escola
4
cola

Exemplo de saída 3

0

Explicação do exemplo 3: “escola” e “cola”, não têm prefixo comum, portanto a resposta é 0.