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:
//package round146;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StringReader;
import java.util.Arrays;

public class C4 {
	BufferedReader br;
	PrintWriter out;
	String INPUT = "";
	
	void solve() throws Exception
	{
//		long S = System.currentTimeMillis();
		char[] str = br.readLine().toCharArray();
//		tr(System.currentTimeMillis()-S);
		SuffixAutomaton2 sa = SuffixAutomaton2.buildSuffixAutomaton(str);
//		tr(System.currentTimeMillis()-S);
		int[] ct = sa.enumNumberOfOccurs();
//		tr(System.currentTimeMillis()-S);
		
		int[] poss = new int[1000001];
		int Q = Integer.parseInt(br.readLine());
		for(int i = 0;i < Q;i++){
			char[] q = br.readLine().toCharArray();
			int cur = 0;
			int m = q.length;
			int pp = 0;
			int l = 0;
			for(int j = 0;j < 2*m-1;j++){
				int e = SuffixAutomaton2.enc(q[j%m]);
				while(cur != 0 && sa.next[cur][e] == -1){
					cur = sa.link[cur];
					l = sa.len[cur];
				}
				if(sa.next[cur][e] != -1){
					cur = sa.next[cur][e];
					l++;
				}
				while(l >= m && sa.len[sa.link[cur]] >= m){
					cur = sa.link[cur];
					l = sa.len[cur];
				}
				if(l >= m){
					poss[pp++] = cur;
				}
			}
			Arrays.sort(poss, 0, pp);
			long ret = 0;
			for(int j = 0;j < pp;j++){
				if(j == 0 || poss[j] != poss[j-1]){
					ret += ct[poss[j]];
				}
			}
			out.println(ret);
		}
//		tr(System.currentTimeMillis()-S);
	}
	
	public static class SuffixAutomaton2 {
		public int size;
		public int[] len; // initialからの最短経路長
		public int[] link; // Failure Link
		public int[][] next; // つぎ
		public int[] original; // clonedの場合original
		
		private SuffixAutomaton2(int sz) {
			size = sz;
			len = new int[sz];
			link = new int[sz];
			next = new int[sz][];
			original = new int[sz];
		}
		
		/**
		 * Suffix Automatonを作成し、トポロジカルソートして返す。
		 * 1文字加える毎にcloneはたかだか1個しか作成されないので全体で2|a|-1個以下しかノードがない。
		 * @param a
		 * @return
		 */
		public static SuffixAutomaton2 buildSuffixAutomaton(char[] a) {
			int n = a.length;
			int[] len = new int[2*n];
			int[] link = new int[2*n];
			int[][] next = new int[2*n][26];
			int[] original = new int[2*n];
			Arrays.fill(link, -1);
			for(int i = 0;i < 2*n;i++){
				Arrays.fill(next[i], -1);
			}
			Arrays.fill(original, -1);
			
			len[0] = 0;
			link[0] = -1;
			int last = 0;
			int sz = 1;
			
			// extend
			for(char c : a){
				int v = enc(c);
				int cur = sz++;
				len[cur] = len[last] + 1;
				int p;
				for(p = last; p != -1 && next[p][v] == -1; p = link[p]){
					next[p][v] = cur;
				}
				if(p == -1){
					link[cur] = 0;
				}else{
					int q = next[p][v];
					if(len[p] + 1 == len[q]){
						link[cur] = q;
					}else{
						int clone = sz++;
						original[clone] = original[q] != -1 ? original[q] : q;
						len[clone] = len[p]+1;
						System.arraycopy(next[q], 0, next[clone], 0, next[q].length);
						link[clone] = link[q];
						for(;p != -1 && next[p][v] == q; p = link[p]){
							next[p][v] = clone;
						}
						link[q] = link[cur] = clone;
					}
				}
				last = cur;
			}
			
			// topological sort
			int[] nct = new int[sz];
			for(int i = 0;i < sz;i++){
				for(int e : next[i]){
					if(e != -1)nct[e]++;
				}
			}
			int[] ord = new int[sz];
			int p = 1;
			ord[0] = 0;
			for(int r = 0;r < p;r++){
				for(int e : next[ord[r]]){
					if(e != -1 && --nct[e] == 0)ord[p++] = e;
				}
			}
			int[] iord = new int[sz];
			for(int i = 0;i < sz;i++)iord[ord[i]] = i;
			
			SuffixAutomaton2 sa = new SuffixAutomaton2(sz);
			for(int i = 0;i < sz;i++){
				sa.len[i] = len[ord[i]];
				sa.link[i] = link[ord[i]] != -1 ? iord[link[ord[i]]] : -1;
				sa.next[i] = next[ord[i]];
				for(int j = 0;j < sa.next[i].length;j++){
					sa.next[i][j] = sa.next[i][j] != -1 ? iord[sa.next[i][j]] : -1;
				}
				sa.original[i] = original[ord[i]] != -1 ? iord[original[ord[i]]] : -1;
			}
			
			return sa;
		}
		
		public static int enc(char c) { return c - 'a'; }
		public static char dec(int n) { return (char)('a'+n); }
		
		public String toString()
		{
			StringBuilder sb = new StringBuilder();
			for(int i = 0;i < size;i++){
				sb.append("{");
				sb.append(i).append("|");
				sb.append("len:").append(len[i]).append(", ");
				sb.append("link:").append(link[i]).append(", ");
				sb.append("original:").append(original[i]).append(", ");
				sb.append("next:{");
				for(int j = 0;j < 26;j++){
					if(next[i][j] != -1){
						sb.append(dec(j)).append(":").append(next[i][j]).append(",");
					}
				}
				sb.append("}}\n");
			}
			return sb.toString();
		}
		
		/**
		 * 各nodeについて、initial->nodeの連続部分文字列が元の文字列に何回出現するかカウントした配列を返す。
		 * cloneされていないノードに1をつけて、len降順に走査してlinkに加算していく。
		 * 同じ文字が現れた時最初のcloneにlinkが集まる仕掛けになっている。あとはlen降順で走査すればオリジナル文字列上のカウントが集まってくる。
		 * @param sa
		 * @return
		 */
		public int[] enumNumberOfOccurs()
		{
			int n = size;
			int[] dp = new int[n];
			for(int i = n-1;i >= 1;i--){
				if(original[i] == -1)dp[i] += 1;
				dp[link[i]] += dp[i];
			}
			return dp;
		}
	}
	
	void run() throws Exception
	{
//		int n = 1000000, m = 99999;
//		Random gen = new Random();
//		StringBuilder sb = new StringBuilder();
//		for(int i = 0;i < n;i++){
//			sb.append((char)('a'+gen.nextInt(3)));
//		}
//		sb.append("\n");
//		sb.append(m + "\n");
//		for(int i = 0;i < m;i++){
//			for(int j = 0;j < 10;j++){
//				sb.append((char)('a'+gen.nextInt(3)));
//			}
//			sb.append("\n");
//		}
//		INPUT = sb.toString();
		
		long S = System.currentTimeMillis();
		br = new BufferedReader(INPUT.isEmpty() ? new InputStreamReader(System.in) : new StringReader(INPUT));
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
		long G = System.currentTimeMillis();
		tr(G-S+"ms");
	}
	
	public static void main(String[] args) throws Exception
	{
		new C4().run();
	}
	
	void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}