Count Matching Subsequences

Given a list of challenge strings and a string T, your task is to count how many challenge strings are subsequences of T. A string \( S = s_1s_2\ldots s_k \) is a subsequence of string \( T = t_1t_2\ldots t_n \) if there exists indices \( 1 \leq i_1 < i_2 < \ldots < i_k \leq n \) such that \( s_1 = t_{i_1}, s_2 = t_{i_2}, ..., s_k = t_{i_k} \). This problem requires you to check each challenge string and determine if it can be derived from T by deleting some (possibly zero) characters without changing the order.

inputFormat

The first line contains an integer \( n \) representing the number of challenge strings. The following \( n \) lines each contain a non-empty challenge string. The last line contains the string \( T \) from which subsequences are to be derived.

outputFormat

Output a single integer: the count of challenge strings that are subsequences of \( T \).

3
abc
def
ghi
abcdeg

1