Description

Old man Marko discovered a new feature on his phone—T9 input. His phone has a keyboard made of digits, which looks like this:

To type a word using this keyboard, Marko needs to press a key multiple times to enter the desired letter. More specifically, if the desired letter is the first letter on the key, he needs to press the key once; if it is the second letter, he needs to press the key twice; and so on.

For example, to type the word giht, Marko needs to press 4 once to type g, then press 4 three times to type i, then press 4 twice to type h, and finally press 8 once to type t.

Marko has memorized the entire dictionary on his phone. The dictionary consists of $N$ words, each word contains only lowercase English letters, and the total length of all words does not exceed $10^9$ characters. Marko will be given a set of available keys, and he wants to know how many words in the dictionary can be typed using only the keys in the given set when using T9 input.

Input Format

The first line contains an integer $N$, representing the number of words in the dictionary.

The next $N$ lines each contain a word consisting of lowercase English letters.

The last line contains a string $S$ consisting of digits 2-9, representing the set of available keys.

Output Format

Output one integer in a single line, representing how many words in the dictionary can be typed using the given set of keys when using T9 input.

3
tomo
mono
dak
6666

1

2
ja
la
52

2

3
dom
fon
tom
366

2

Hint

[Sample 1 Explanation]

All four letters in mono are on key 6, so mono can be typed.

All other words cannot be typed.

[Sample 2 Explanation]

j is on key 5 and a is on key 2, so ja can be typed.

l is on key 5 and a is on key 2, so la can be typed.

[Constraints]

For $100\%$ of the testdata, $1 \le N \le 10^3，1 \le |S| \le 10^3$.

[Note]

The scoring of the subtasks follows the original problem, with a full score of 50.

This problem is translated from COCI 2015-2016 CONTEST #2 T1 MARKO.

Translated by ChatGPT 5