Codeforces Round 146 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

string suffix structures

strings

*2700

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Cyclical Quest

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputSome 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".

Input

The first line contains a non-empty string *s*. The length of string *s* is not greater than 10^{6} characters.

The second line contains an integer *n* (1 ≤ *n* ≤ 10^{5}) — 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 10^{6} characters.

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

Output

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.

Examples

Input

baabaabaaa

5

a

ba

baa

aabaa

aaba

Output

7

5

7

3

5

Input

aabbaa

3

aa

aabb

abba

Output

2

3

3

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/29/2023 11:41:28 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|