Mirko's ASCII street is made of ~N~ lowercase letters of the English alphabet. The city government occasionally replaces the tiles in the street. However, the letter tiles are in high demand, so the government has only ~M~ different tile patterns available.

The ~i^\text{th}~ tile pattern consists of ~L_i~ letters. A tile cannot be rotated or broken into pieces, and it can only be placed such that the tile letters coincide with the contiguous letter subsequence in the street. Tiles can overlap and we can use multiple tiles of the same pattern.

A street cell is untileable if it cannot be covered by any tile. Compute the number of untileable cells.

Input Specification

The first line of input contains the positive integer ~N~ ~(1 \leq N \leq 300\,000)~, the length of the street.

The second line of input contains ~N~ lowercase English letters, the letter sequence in the street.

The third line of input contains the positive integer ~M~ ~(1 \leq M \leq 5\,000)~, the number of tile patterns.

Each of the next ~M~ lines contains a description of a tile pattern with length ~L_i~ ~(1 \leq L_i \leq 5\,000)~. The tile pattern descriptions consist of lowercase English letters.

Output Specification

The first and only line of output must contain the required number of untileable cells.

Sample Input 1

6
abcbab
2
cb
cbab

Sample Output 1

2

Sample Input 2

4
abab
2
bac
baba

Sample Output 2

4

Sample Input 3

6
abcabc
2
abca
cab

Sample Output 3

1