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,200\,000~) 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