题目描述

给定一个主串 $S$ 和 $n$ 个询问串，求每个询问串的所有循环同构在主串中出现的次数总和。

输入格式

第一行一个字符串 $S$，长度不超过 $10^6$。

第二行一个整数 $n$，$1\le n\le 10^5$。

接下来 $n$ 行，每行一个长度不超过 $10^6$ 的字符串，表示一个询问。所有字符串仅包含小写字母。

输出格式

对于每一个询问，在一行中输出一个整数表示答案。

baabaabaaa
5
a
ba
baa
aabaa
aaba

7
5
7
3
5

aabbaa
3
aa
aabb
abba

2
3
3