Problem1346--PIPI的字符串问题Ⅳ

1346: PIPI的字符串问题Ⅳ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 623  Solved: 205
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI来考察大家字符串处理的能力啦。
给定一个字符串S,以及q次询问。
每次询问给出一个字符串T,你需要回答,对于T中的所有子串,有几个子串同S循环同构。
提示:对于一个字符串a,每次把a的第一个字符移动到最后一个,如果操作若干次后能够得到字符串b,则a和b循环同构。
所有字符都是小写英文字母

Input

第一行给出字符串S。|S|<=1e6.
第二行给出询问次数q,q<=1e6.
接下来每行给出字符串T,|T|<=1e6.
题目保证所有询问|T|之和<=1e7.

Output

对于每个询问,输出一个整数表示答案。

Sample Input

abab
2
abababab
ababcbaba

Sample Output

5
2

Source/Category

中等