Problem: 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 xi, for each string xi find, how many consecutive substrings of s are cyclical isomorphic to xi.

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 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 xi — the string for the i-th query. The total length of xi is less than or equal to 106 characters.

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

Output

For each query xi print a single integer that shows how many consecutive substrings of s are cyclical isomorphic to xi. 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

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.StringTokenizer;

/**
 * 235C
 * θ(|s| + Σ(|x_i|)) time
 * θ(|s| + n + max(|x_i|)) space
 *
 * @author artyom
 */
public class _235C implements Runnable {
    private BufferedReader in;
    private StringTokenizer tok;

    private Object solve() throws IOException {
        String s = nextToken() + '{';
        SuffixTreeNode root = buildSuffixTree(s);
        preprocess(root);
        StringBuilder sb = new StringBuilder();
        for (int k = 0, n = nextInt(); k < n; k++) {
            String t = nextToken();
            long cnt = 0;
            SuffixTreeNode v = root;
            out:
            for (int j = 0, x = calcNumberOfUniqueCyclicStrings(t), i = 0, p = 0, m = t.length(); j < x; j++) {
                if (j > 0) {
                    if (v == root) {
                        p = Math.max(0, p - 1);
                    } else {
                        v = v.suffixLink;
                    }
                    while (p > 0) {
                        SuffixTreeNode next = v.children[t.charAt((v.depth() + j) % m) - 'a'];
                        if (next.length() <= p) {
                            p -= next.length();
                            v = next;
                        } else {
                            int r = next.start + p;
                            for (; r < next.end && i < m + j; r++, i++) {
                                if (s.charAt(r) != t.charAt(i % m)) {
                                    p = r - next.start;
                                    continue out;
                                }
                            }
                            if (i == m + j) {
                                cnt += next.leaves;
                                if (r == next.end) {
                                    v = next;
                                    p = 0;
                                } else {
                                    p = r - next.start;
                                }
                                continue out;
                            }
                            v = next;
                            break;
                        }
                    }
                }
                while (true) {
                    SuffixTreeNode next = v.children[t.charAt(i % m) - 'a'];
                    if (next == null) {
                        p = 0;
                        break;
                    }
                    int r = next.start;
                    for (; r < next.end && i < m + j; r++, i++) {
                        if (s.charAt(r) != t.charAt(i % m)) {
                            p = r - next.start;
                            continue out;
                        }
                    }
                    if (i == m + j) {
                        cnt += next.leaves;
                        if (r == next.end) {
                            v = next;
                            p = 0;
                        } else {
                            p = r - next.start;
                        }
                        continue out;
                    }
                    v = next;
                }
            }

            sb.append(cnt).append('\n');
        }
        return sb;
    }

    private static void preprocess(SuffixTreeNode node) {
        if (node.isLeaf()) {
            node.leaves = 1;
        } else {
            for (SuffixTreeNode child : node.children) {
                if (child != null) {
                    preprocess(child);
                    node.leaves += child.leaves;
                }
            }
        }
    }

    //--------------------------------------------------------------
    public static void main(String[] args) {
        new _235C().run();
    }

    @Override
    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            tok = null;
            System.out.print(solve());
            in.close();
        } catch (IOException e) {
            System.exit(0);
        }
    }

    private String nextToken() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    /**
     * O(|str|).
     */
    private static int calcNumberOfUniqueCyclicStrings(String str) {
        int[] z = calcZ(str);
        int n = str.length();
        int[] p = new int[n];
        for (int i = 1; i < n; i++) {
            for (int j = i, k = 2; z[i] >= j && p[i + j - 1] == 0; k++, j += i) {
                p[i + j - 1] = i;
            }
        }
        return p[n - 1] > 0 ? p[n - 1] : n;
    }

    @SuppressWarnings("Duplicates")
    private static int[] calcZ(String s) {
        int[] z = new int[s.length()];
        for (int l = 0, r = 0, n = z.length, k = 1; k < n; k++) {
            if (k > r) {
                int b = 0, q = k;
                while (q < n && s.charAt(q) == s.charAt(b)) {
                    q++;
                    b++;
                }
                if (b > 0) {
                    z[k] = b;
                    l = k;
                    r = q - 1;
                }
            } else {
                int v = z[k - l], b = r - k + 1;
                if (v < b) {
                    z[k] = v;
                } else {
                    int q = r + 1;
                    while (q < n && s.charAt(q) == s.charAt(b)) {
                        q++;
                        b++;
                    }
                    z[k] = b;
                    l = k;
                    r = q - 1;
                }
            }
        }
        return z;
    }

    @SuppressWarnings("ConstantConditions")
    private static SuffixTreeNode buildSuffixTree(CharSequence s) {
        int n = s.length();
        byte[] a = new byte[n];
        for (int i = 0; i < n; i++) {
            a[i] = (byte) (s.charAt(i) - 'a');
        }
        SuffixTreeNode root = new SuffixTreeNode(0, 0, 0, null, null);
        SuffixTreeNode node = root;
        for (int i = 0, tail = 0; i < n; i++, tail++) {
            SuffixTreeNode last = null;
            while (tail >= 0) {
                SuffixTreeNode ch = node.children[a[i - tail]];
                while (ch != null && tail >= ch.length()) {
                    tail -= ch.length();
                    node = ch;
                    ch = ch.children[a[i - tail]];
                }
                if (ch == null) {
                    node.children[a[i]] = new SuffixTreeNode(i, n, node.depth(), i, node);
                    if (last != null) {
                        last.suffixLink = node;
                    }
                    last = null;
                } else {
                    byte t = a[ch.start + tail];
                    if (t == a[i]) {
                        if (last != null) {
                            last.suffixLink = node;
                        }
                        break;
                    } else {
                        SuffixTreeNode splitNode = new SuffixTreeNode(ch.start, ch.start + tail, node.depth(), null, node);
                        splitNode.children[a[i]] = new SuffixTreeNode(i, n, ch.depth + tail, i, splitNode);
                        splitNode.children[t] = ch;
                        ch.start += tail;
                        ch.depth += tail;
                        ch.parent = splitNode;
                        node.children[a[i - tail]] = splitNode;
                        if (last != null) {
                            last.suffixLink = splitNode;
                        }
                        last = splitNode;
                    }
                }
                if (node == root) {
                    tail--;
                } else {
                    node = node.suffixLink;
                }
            }
        }
        return root;
    }

    private static final class SuffixTreeNode {
        int depth; // The number of characters from root to this node
        int start; // Inclusive
        int end; // Exclusive
        Integer position;
        SuffixTreeNode parent;
        final SuffixTreeNode[] children;
        SuffixTreeNode suffixLink;
        // Additional properties
        int leaves;

        private SuffixTreeNode(int start, int end, int depth, Integer position, SuffixTreeNode parent) {
            this.start = start;
            this.end = end;
            this.parent = parent;
            this.depth = depth;
            if (position == null) {
                this.position = null;
                this.children = new SuffixTreeNode[27];
            } else {
                this.position = position - depth;
                // Save some space and time
                this.children = null;
            }
        }

        boolean isLeaf() {
            return position != null;
        }

        /**
         * @return the number of characters on the edge to the parent.
         */
        final int length() {
            return end - start;
        }

        /**
         * @return the number of characters on the path from the root to this node.
         */
        final int depth() {
            return depth + end - start;
        }

        @Override
        public String toString() {
            return "(" + start + ',' + (end - 1) + ')';
        }
    }
}