892. Find the Toy

0

Medium

Alice loves a particular toy whose name is favToy.
Her mother tell her that she will only buy the favToy to Alice if she correctly answer her question.
Her mother gives a list of toy names toyList.
Alice have to find the number of toyList[i] that is a subsequence of favToy. Help Alice to get her favToy.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Input Format

First line of input contains a string favToy.
Second line of input contains a integer n number of toys in toyList.
Following n lines contains a string toy.

Output Format

Return an integer denoting number of toyList[i] that is a subsequence of favToy.

Example

Input

"abcde" 4 "a" "bb" "acd" "ace"

Output

3

Constraints

1 <= favToy.length <= 5 * 10^4
1 <= toyList.length <= 5000
1 <= toyList[i].length <= 50
favToy and toyList[i] consist of only lowercase English letters.