CF235C.Cyclical Quest

Some days ago, WJMZBMR learned how to answer the query "how many times does a string x occur in a string s" quickly by preprocessing the string s. But now he wants to make it harder.

So he wants to ask "how many consecutive substrings of s are cyclical isomorphic to a given string x". You are given string s and n strings x__i, for each string x__i find, how many consecutive substrings of s are cyclical isomorphic to x__i.

Two strings are called cyclical isomorphic if one can rotate one string to get the other one. 'Rotate' here means 'to take some consecutive chars (maybe none) from the beginning of a string and put them back at the end of the string in the same order'. For example, string "abcde" can be rotated to string "deabc". We can take characters "abc" from the beginning and put them at the end of "de".

几天前，WJMZBMR 学会了通过预处理字符串 $s$ 来快速回答查询：“字符串 $x$ 在字符串 $s$ 中出现了多少次”。但现在他想让问题变得更难。

因此，他希望提出这样的问题：“字符串 $s$ 中有多少个连续子串与给定字符串 $x$ 是循环同构的？”
你将被给定字符串 $s$ 和 $n$ 个字符串 $x_i$；对每个字符串 $x_i$，请找出 $s$ 中有多少个连续子串与 $x_i$ 循环同构。

若一个字符串可通过旋转得到另一个字符串，则称这两个字符串是循环同构的。“旋转”是指：从字符串开头取若干个（可能为零个）连续字符，并以相同顺序将其移至字符串末尾。例如，字符串 "abcde" 可通过旋转得到 "deabc"：我们可取开头的 "abc" 并将其置于 "de" 的末尾。

The first line contains a non-empty string s. The length of string s is not greater than 106 characters.

The second line contains an integer n (1 ≤ n ≤ 105) — the number of queries. Then n lines follow: the i-th line contains the string x__i — the string for the i-th query. The total length of x__i is less than or equal to 106 characters.

In this problem, strings only consist of lowercase English letters.

第一行包含一个非空字符串 $s$。字符串 $s$ 的长度不超过 $10^6$ 个字符。

第二行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 查询的次数。随后是 $n$ 行：第 $i$ 行包含字符串 $x_i$ —— 第 $i$ 次查询所用的字符串。所有 $x_i$ 的总长度不超过 $10^6$ 个字符。

本题中，字符串仅由小写英文字母组成。

For each query x__i print a single integer that shows how many consecutive substrings of s are cyclical isomorphic to x__i. Print the answers to the queries in the order they are given in the input.

对于每个查询 $x_i$，输出一个整数，表示字符串 $s$ 中有多少个连续子串与 $x_i$ 是循环同构的。请按照输入中查询给出的顺序输出对应答案。