前几天,WJMZBMR 学会了如何通过预处理字符串 s 来快速回答“字符串 x 在字符串 s 中出现了多少次”的查询。但现在他想让事情变得更难。
所以他想问“s中有多少个连续子串与给定的字符串x循环同构”。给定字符串 s 和 n 个字符串 xi,对于每个字符串 xi 求出 s 中有多少个连续子串与 xi 循环同构。
如果两个字符串可以旋转一个字符串以获得另一个字符串,则称为循环同构。这里的“旋转”意味着“从字符串的开头取出一些连续的字符(可能没有),并以相同的顺序将它们放回字符串的末尾”。例如,字符串“abcde”可以旋转为字符串“deabc”。我们可以从开头取出字符“abc”并将它们放在“de”的末尾。
输入
第一行包含一个非空字符串 s。字符串 s 的长度不大于 106 个字符。
第二行包含一个整数 n (1 ≤ n ≤ 105) — 查询数量。然后是 n 行:第 i 行包含字符串 xi — 第 i 个查询的字符串。 xi 的总长度小于或等于 106 个字符。
在这个问题中,字符串仅由小写英文字母组成。
输出
对于每个查询 xi 打印一个整数,该整数显示 s 中有多少个连续子串与 xi 循环同构。按照输入中给出的顺序打印查询的答案。
示例
输入 #1
baabaabaaa 5 a ba baa aabaa aaba
输出 #1
7 5 7 3 5
输入 #2
aabbaa 3 aa aabb abba
输出 #2
2 3 3