IOI '96 - Veszprém, Hungary

The structure of some biological objects is represented by the sequence of their constituents, where each part is denoted by an uppercase letter. Biologists are interested in decomposing a long sequence into shorter ones called primitives.

We say that a sequence $S$ can be composed from a given set of primitives $P$ if there is a sequence of (possibly repeated) primitives from the set whose concatenation equals $S$. Not necessarily all primitives need be present. For instance the sequence ABABACABAAB can be composed from the set of primitives:

{A, AB, BA, CA, BBC}

The first $K$ characters of $S$ are the prefix of $S$ with length $K$. Write a program which accepts as input a set of primitives and a sequence of constituents and then computes the length of the longest prefix that can be composed from primitives.

Input Specification

First, the input contains the list (length $1,\dots ,200$) of primitives (length $1,\dots ,10$) expressed as a series of space-separated strings of uppercase characters on one or more lines. The list of primitives is terminated by a line that contains nothing more than a period (.). No primitive appears twice in the list.

Then, the input contains a sequence $S$ (length $1,\dots ,200000$) expressed as one or more lines, none of which exceeds $76$ letters in length. Newline characters are not part of the string $S$.

Output Specification

A single line containing an integer that is the length of the longest prefix that can be composed from the set $P$.

Sample Input

A AB BA CA BBC
.
ABABACABAABC

Sample Output

11