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.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Random;
import java.io.Writer;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskC {
	public void solve(int testNumber, InputReader in, OutputWriter out) {
        String S = in.next(), x;
        int n = in.nextInt();

        StringUtils.SuffixAutomaton sa  = new StringUtils.SuffixAutomaton('a','z');
        sa.add(S.toCharArray());
        sa.recalcSizes();
        
        int i,j,k;
        for(i=0;i<n;++i){
            x = in.next();
            int m = x.length();
            x+=x;
            char c[] = x.toCharArray();
            
            int z[] = StringUtils.zFunction(c);
            for(j=1;j<m;++j) if(z[j]>=m) break;
            int end = j;

            long ans = 0;
            int t = sa.nil, q;
            int len = 0;
            for(k=0;k<c.length;++k) if(k-m+1<end){
                while(t!=-1 && sa.to[c[k]-'a'][t]==sa.nil) t = sa.link[t];
                if(t==-1){
                    t = sa.nil;
                    len = 0;
                }else{
                    len = Math.min(len, sa.length[t]);
                    t = sa.to[c[k]-'a'][t];
                    ++len;
                }
                if(k-m+1>=0 && len>=m){
                    q = t;
                    while(q!=-1 && sa.length[q]>=m && sa.length[sa.link[q]]>=m) q = sa.link[q];
                    if(q==-1) q = sa.nil;
                    if(sa.length[q]>=m) ans+=sa.size[q];
                    t = q;
                }
            }

            

            out.writeln(ans);
        }
	}
    
    }

class InputReader{
    private InputStream in;
    private byte buffer[] = new byte[1<<11];
    private int cur;
    private int end;
    
    
    public InputReader(InputStream stream){
        in = stream;
    }
    
    public int read(){
        if(end<0) throw new InputMismatchException();
        if(cur>=end){
            cur = 0;
            try{
                end = in.read(buffer);
            }catch(IOException e){
                throw new InputMismatchException();
            }
            if(end<=0) return -1;
        }
        return buffer[cur++];
    }
    
    public boolean isSpace(int c){
        return c==' ' || c=='\n' || c=='\r' || c=='\t' || c==-1;
    }
    
    public String next(){
        StringBuilder s = new StringBuilder();
        int c = read();
        while(isSpace(c)) c = read();
        do{
            s.append((char)c);
            c = read();
        }while(!isSpace(c));
        return s.toString();
    }
    
    public int nextInt(){
        int c = read(), res = 0, sign = 1;
        while(isSpace(c)) c = read();
        if(c=='-'){ sign = -1; c = read(); }
        do{
            if(c>'9' || c<'0') throw new InputMismatchException();
            res = res*10 + (c-'0');
            c = read();
        }while(!isSpace(c));
        return res*sign;
    }

    }

class OutputWriter{
    private PrintWriter out;
    
    public OutputWriter(Writer out){
        this.out = new PrintWriter(out);
    }

    public OutputWriter(OutputStream out){
        this.out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(out)));
    }
    
    public void close(){
        out.close();
    }

    public void write(Object ... o){
        for(Object x : o) out.print(x);
    }
    
    public void writeln(Object ... o){
        write(o);
        out.println();
    }
}

class StringUtils{
    
    public static int[] zFunction(char s[]){
        int n = s.length, i, j;
        int z[] = new int[n];
        z[0] = j = 0;
        for(i=1; i<n; ++i){
            int k = Math.max(0, Math.min(z[i-j], j+z[j]-i));
            while(i+k<n && s[k]==s[i+k]) ++k;
            if(i+k > j+z[j]) j = i;
            z[i] = k;
        }
        return z;
    }
    
    
    
    
    
    
    
    public static class SuffixAutomaton{
        private int N, M;
        private char minChar, maxChar;
        public int length[];
        public int link[];
        public int to[][];
        public int last;
        public int nil;
        
        public int size[];
        
        public SuffixAutomaton(char minChar, char maxChar){
            this.maxChar = maxChar;
            this.minChar = minChar;
            nil = 0;
            last = nil;
            N = 1;
            M = (int) 2e6;
            length = new int[M];
            link = new int[M];
            link[nil] = -1;
            to = new int[maxChar-minChar+1][M];
            
            size = new int[M];
        }
        
        private int newState(){
            if(N==M){
                length = Arrays.copyOf(length, M<<1);
                link = Arrays.copyOf(link, M<<1);
                for(char c = minChar; c<=maxChar; ++c) to[c] = Arrays.copyOf(to[c-minChar], M<<1);
                size = Arrays.copyOf(size, M<<1);
                M<<=1;
            }
            return N++;
        }
        
        public void add(char c){
            c-=minChar;
            int current = newState();
            length[current] = length[last]+1;
            link[current] = nil;
            for(; last!=-1 && to[c][last]==nil; last = link[last]) to[c][last] = current;
            if(last!=-1){
                int p = to[c][last];
                if(length[p]==length[last]+1) link[current] = p; else{
                    int q = newState();
                    length[q] = length[last]+1;
                    link[q] = link[p];
                    for(char x=minChar; x<=maxChar; ++x) to[x-minChar][q] = to[x-minChar][p];
                    for(; last!=-1 && to[c][last]==p; last = link[last]) to[c][last] = q;
                    link[current] = link[p] = q;
                }
            }
            last = current;
        }
        
        public void add(char s[]){
            for(char c : s) add(c);
        }
        
        private void dfs(int v){
            for(char c = 0; c<=maxChar-minChar; ++c) if(to[c][v]!=nil){
                if(size[to[c][v]]==0) dfs(to[c][v]);
                size[v]+=size[to[c][v]];
            }
            if(st==v){
                ++size[v];
                st = link[st];
            }
        }
        private int st;
        public void recalcSizes(){
            st = last;
            dfs(nil);
        }
    }
    
    
    }