题目描述

给定 $n$ 个由小写英文字母组成的模式串，以及一个文本串 $T$。对每个模式串，请你求出它在 $T$ 中出现的次数（允许重叠，按出现位置计数；相同的模式串分别计数）。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行一个模式串。

最后一行一个字符串 $T$。

输出格式

共 $n$ 行，第 $i$ 行为第 $i$ 个模式串在 $T$ 中出现的次数。

输入输出样例 #1

输入 #1

2
a
ab
ababa

输出 #1

3
2

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 2\times 10^5$，所有模式串的长度之和不超过 $2\times 10^5$，$|T|\le 2\times 10^5$。