Morse

Morse code is a method of transmitting text information as a series of on-off tones, lights, or clicks that can be directly understood by a skilled listener or observer without special equipment. It works by mapping each letter of the English alphabet to a sequence of up to 4 characters, either dashes or dots.

Because of the non-constant sequence sizes, different letter encodings must be separated in order to prevent ambiguity.

For instance, the sequence —•—••— may have different interpretations, depending on how one chooses to separate the symbols:

(—•—•) (•—)
ca
(—•) (—•) (•—)
nna
(—•—•) (•) (—)
cet
(—•) (—•) (•) (—)
nnet

Two words are called similar if they have the same Morse representation, without symbol separation. In the example above, ca, nna, cet and nnet are all similar to each other.

You are given a set containing N different words. Your task is to find the largest subset such that any two words in the subset are similar.

Input

The first 26 lines of input contain each letter of the alphabet, along with its Morse encoding.

The next line contains N. Each of the following N lines contains a word.

Output

A single integer: the size of the largest subset in which any two words are similar to each other.
If there are no similar words, the answer is -1.

Constraints

  • Sum of all word lengths ≤ 105
  • All words contain only lowercase English letters.

Sample

InputOutputExplanation
a .-
b -...
c -.-.
d -..
e .
f ..-.
g --.
h ....
i ..
j .---
k -.-
l .-..
m --
n -.
o ---
p .--.
q --.-
r .-.
s ...
t -
u ..-
v ...-
w .--
x -..-
y -.--
z --..
5
ca
nna
abc
nnet
cat
3 Words ca, nna and nnet are all represented in Morse as —.—..—.
They form the largest subset with the required property.
Words abc (•——•••—•—•) and cat (—•—••——) have unique representations.
Questions?

Sponsors Gold