我们将字符串 s[a, b] = sasa + 1... sb (1 ≤ a ≤ b ≤ |s|) 称为字符串 s = s1s2... s|s| 的子字符串,其中 |s|是字符串 s 的长度。
非空字符串 t 的踪迹是该字符串组成的一组字符。例如,字符串“aab”的踪迹等于{'a', 'b'}。
让我们考虑一个任意字符串 s 及其踪迹等于 C 的子串集合。我们将通过包含 r(C, s) 来表示该集合中最大子串的数量。属于某个集合的长度为 n = b - a + 1 的子串 s[a, b] 称为包含最大子串,如果该集合中不存在长度大于 n 的子串 s[x, y],使得 1 ≤ x ≤ a ≤ b ≤ y ≤ |s|。字符串 s 的两个子串即使相等但位于 s 的不同位置,也被认为是不同的。
Polycarpus 在弦乐考试中遇到了一项具有挑战性的实践任务。他必须执行以下操作:给定字符串 s 和非空字符集 C1, C2, ..., Cm,找到每个集合 Ci 的 r(Ci, s)。帮助波利卡普斯解决问题,因为他真的不想被大学开除并去参军!
输入
第一行包含一个非空字符串 s (1 ≤ |s| ≤ 106)。
第二行包含一个整数 m (1 ≤ m ≤ 104)。接下来的 m 行包含集合 Ci 的描述。第 i 行包含字符串 ci,其踪迹等于 Ci。保证每个字符串ci的所有字符都不同。
请注意,Ci 不一定不同。所有给定的字符串均由小写英文字母组成。
输出
打印 m 个整数 — 第 i 个整数必须等于 r(Ci, s)。
示例
输入 #1
aaaaa 2 a a
输出 #1
1 1
输入 #2
abacaba 3 ac ba a
输出 #2
1 2 4