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*<sub class="lower-index">*i*</sub>, for each string *x*<sub class="lower-index">*i*</sub> find, how many consecutive substrings of *s* are cyclical isomorphic to *x*<sub class="lower-index">*i*</sub>.

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".
The first line contains a non-empty string *s*. The length of string *s* is not greater than 10<sup class="upper-index">6</sup> characters.

The second line contains an integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>) — the number of queries. Then *n* lines follow: the *i*-th line contains the string *x*<sub class="lower-index">*i*</sub> — the string for the *i*-th query. The total length of *x*<sub class="lower-index">*i*</sub> is less than or equal to 10<sup class="upper-index">6</sup> characters.

In this problem, strings only consist of lowercase English letters.
class FenwickTree:
    def __init__(self, nums):
        n = len(nums)
        self.n = n
        self.bit = nums[:]
        self.build()
    
    def build(self):
        for i in range(self.n):
            j = i | (i + 1)
            if j < self.n:
                self.bit[j] += self.bit[i]

    def sum(self, r):
        res = 0
        while r >= 0:
            res += self.bit[r]
            r = (r & (r + 1)) - 1
        return res

    def rsum(self, l, r):
        return self.sum(r) - self.sum(l - 1)

    def add(self, idx, delta):
        while idx < self.n:
            self.bit[idx] += delta
            idx = idx | (idx + 1)

def sa_naive(s):
    n = len(s)
    return sorted(range(n), key=lambda i: s[i:])

def sa_doubling(s):
    def key(i):
        if i + k < n:
            return rank[i], rank[i + k]
        return rank[i], -1

    smax = max(s) + 1
    n = len(s)
    sa = list(range(n))
    rank = s[:]
    tmp = [0] * n

    k = 1
    while k < n:
        sa.sort(key=key)
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i-1]] + (key(sa[i-1]) < key(sa[i]))
        rank, tmp = tmp, rank
        k <<= 1
    return sa

def sa_is(s, upper, THRESHHOLD_NAIVE=20, THRESHHOLD_DOUBLE=100):
    def induce(lms):
        for i in range(n):
            sa[i] = -1
        buf = sum_s[:]
        for d in lms:
            if d == n:
                continue
            sa[buf[s[d]]] = d
            buf[s[d]] += 1

        buf = sum_l[:]
        sa[buf[s[n - 1]]] = n - 1
        buf[s[n - 1]] += 1
        for i in range(n):
            v = sa[i]
            if v >= 1 and not ls[v - 1]:
                sa[buf[s[v - 1]]] = v - 1
                buf[s[v - 1]] += 1

        buf = sum_l[:]
        for i in range(n)[::-1]:
            v = sa[i]
            if v >= 1 and ls[v - 1]:
                buf[s[v - 1] + 1] -= 1
                sa[buf[s[v - 1] + 1]] = v - 1

    n = len(s)
    if n == 0:
        return []
    if n == 1:
        return [0]
    if n <= THRESHHOLD_NAIVE:
        return sa_naive(s)
    if n <= THRESHHOLD_DOUBLE:
        return sa_doubling(s)

    sa = [0] * n
    ls = [0] * n
    for i in range(n - 1)[::-1]:
        if s[i] == s[i + 1]:
            ls[i] = ls[i + 1]
        else:
            ls[i] = int(s[i] < s[i + 1])

    sum_l = [0] * (upper + 1)
    sum_s = [0] * (upper + 1)
    for i, x in enumerate(ls):
        if not x:
            sum_s[s[i]] += 1
        else:
            sum_l[s[i] + 1] += 1
    for i in range(upper + 1):
        sum_s[i] += sum_l[i]
        if i < upper:
            sum_l[i + 1] += sum_s[i]

    lms_map = [-1] * (n + 1)
    lms = []
    m = 0
    for i in range(1, n):
        if not ls[i - 1] and ls[i]:
            lms_map[i] = m
            lms.append(i)
            m += 1

    induce(lms)

    if m:
        sorted_lms = []
        for v in sa:
            if v == -1:
                print("minuse")
            if lms_map[v] != -1:
                sorted_lms.append(v)

        rec_s = [0] * m
        rec_upper = 0
        rec_s[lms_map[sorted_lms[0]]] = 0
        for i in range(1, m):
            l = sorted_lms[i - 1]
            r = sorted_lms[i]
            end_l = lms[lms_map[l] + 1] if lms_map[l] + 1 < m else n
            end_r = lms[lms_map[r] + 1] if lms_map[r] + 1 < m else n
            same = 1
            if end_l - l != end_r - r:
                same = 0
            else:
                while l < end_l:
                    if s[l] != s[r]:
                        break
                    l += 1
                    r += 1
                if l == n or s[l] != s[r]:
                    same = 0
            if not same:
                rec_upper += 1
            rec_s[lms_map[sorted_lms[i]]] = rec_upper

        rec_sa = sa_is(rec_s, rec_upper)
        for i in range(m):
            sorted_lms[i] = lms[rec_sa[i]]
        induce(sorted_lms)
    return sa

def suffix_array(S, compress=True):
    if compress:
        ch = sorted(set(S))
        ctoi = {c: i for i, c in enumerate(ch, 1)}
        S = [ctoi[s] for s in S]

    upper = max(S) + 1
    return sa_is(S, upper)

def construct_lcp(s, sa):
    n = len(s)
    assert(n >= 1)
    rank = [0] * n
    for i in range(n):
        rank[sa[i]] = i

    lcp = [0] * n
    h = 0
    for i in range(n):
        if h > 0:
            h -= 1
        if rank[i] == 0:
            continue
        j = sa[rank[i] - 1]
        while j + h < n and i + h < n:
            if s[j + h] != s[i + h]:
                break
            h += 1
        lcp[rank[i] - 1] = h
    return lcp

class SparseTable:
    def __init__(self, data, merge_method):
        self.note = [0] * (len(data) + 1)
        self.merge_method = merge_method
        l, r, v = 1, 2, 0
        while True:
            for i in range(l, r):
                if i >= len(self.note):
                    break
                self.note[i] = v
            else:
                l *= 2
                r *= 2
                v += 1
                continue
            break
        self.ST = [[0] * len(data) for _ in range(self.note[-1]+1)]
        self.ST[0] = data
        for i in range(1, len(self.ST)):
            for j in range(len(data) - (1 << i) + 1):
                self.ST[i][j] = merge_method(self.ST[i-1][j], self.ST[i-1][j + (1 << (i-1))])

    def query(self, l, r):
        r -= 1
        pos = self.note[r-l+1]
        return self.merge_method(self.ST[pos][l], self.ST[pos][r - (1 << pos) + 1])

class Problem:
    def __init__(self, S, lbl, lens, n, m):
        self.s = S
        self.labels = lbl
        self.length = lens
        self.n = n
        self.m = m
        self.sa = suffix_array(S)
        self.lcp = construct_lcp(S, self.sa)
        self.table = SparseTable(self.lcp, min)
        self.tree = FenwickTree([1 if self.sa[i] < m else 0 for i in range(len(S))])

    def check(self, x, k):
        left = x
        right = len(self.s) - 1
        while left < right - 1:
            mid = (left + right) >> 1
            if self.table.query(x, mid) >= k:
                left = mid
            else:
                right = mid - 1
 
        if self.table.query(x, right) >= k:
            R = right
        else:
            R = left
 
        left = 0
        right = x
        while left < right - 1:
            mid = (left + right) >> 1
            if self.table.query(mid, x) >= k:
                right = mid
            else:
                left = mid + 1
 
        if self.table.query(left, x) >= k:
            L = left
        else:
            L = right
        return self.tree.rsum(L, R)
 
    def solve(self):
        ans = [0] * self.n
        last = [-1] * self.n
        for j in range(len(self.sa)):
            i = self.sa[j]
            lbl = self.labels[i]
            if lbl != -1 and (last[lbl] == -1 or self.table.query(last[lbl], j) < self.length[lbl]):
                ans[lbl] += self.check(j, self.length[lbl])
                last[lbl] = j
        for i in ans:
            print(i)
 
import sys
input = lambda : sys.stdin.readline().strip()

s = input().strip()
n = int(input())
S = [s]
lbl = []
lens = []
m = len(s)
for _ in range(m):
    lbl.append(-1)
 
for i in range(n):
    w = input()
    strlen = len(w)
    S.append('*')
    S.append(w)
    S.append(w)
    lens.append(strlen)
    lbl.append(-1)
    lbl += [i] * strlen
    lbl += [-1] * strlen
 
S.append('$')
lbl.append(-1)
s = ''.join(S)
p = Problem(s, lbl, lens, n, m)
p.solve()