试题来源：https://loj.ac/p/2505，向 LOJ 和出题人表示感谢。如果版权方并不希望试题出现在洛谷，可联系洛谷管理组撤下试题。
黎瑟最近在机器遗忘平台 IQ-- 上租了一台服务器来训练她的梯度上升算法，服务器上存着很大的数据集。由于这些数据集里大部分数据都有很大的相似性，所以这些数据都以一种压缩比很高的方式压缩了起来。
形式化地说，压缩算法会存储一个包含 个字符串的字典 ，而数据是用一个序列 表示的，数据解压后的内容为 。
黎瑟本地硬盘的空间并不富裕，网络条件也不好，因此她只能不断向服务器发送请求，每次询问一个字符串 在数据中的出现次数。
但数据解压后的长度实在太大，普通的朴素算法无法工作，为了让她顺利的把实验数据给你写论文，帮她实现这个算法吧。
下面形式化地给出题意：给定 个字符串 和 个 之间的整数 ，令母串为 ，回答 次询问，每次给出一个字符串 ，询问这个串在母串中的出现次数。请注意 和 都只由字母 a,b 组成。
