You've got a string s = s1s2... s|s| of length |s|, consisting of lowercase English letters. There also are q queries, each query is described by two integers li, ri (1 ≤ li ≤ ri ≤ |s|). The answer to the query is the number of substrings of string s[li... ri], which are palindromes.

String s[l... r] = slsl + 1... sr (1 ≤ l ≤ r ≤ |s|) is a substring of string s = s1s2... s|s|.

String t is called a palindrome, if it reads the same from left to right and from right to left. Formally, if t = t1t2... t|t| = t|t|t|t| - 1... t1.

Input

The first line contains string s (1 ≤ |s| ≤ 5000). The second line contains a single integer q (1 ≤ q ≤ 106) — the number of queries. Next q lines contain the queries. The i-th of these lines contains two space-separated integers li, ri (1 ≤ li ≤ ri ≤ |s|) — the description of the i-th query.

It is guaranteed that the given string consists only of lowercase English letters.

Output

Print q integers — the answers to the queries. Print the answers in the order, in which the queries are given in the input. Separate the printed numbers by whitespaces.

Examples

Input

caaaba
5
1 1
1 4
2 3
4 6
4 5


Output

1
7
3
4
2

Note

Consider the fourth query in the first test case. String s[4... 6] = «aba». Its palindrome substrings are: «a», «b», «a», «aba».
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Stream;

public class Solution implements Runnable {

	static final long MOD = Long.MAX_VALUE;
	static final Reader in = new Reader();
	static final PrintWriter out = new PrintWriter(System.out);
	StringBuilder answer = new StringBuilder();

	public static void main(String[] args) {
		// long startt = System.nanoTime();
		new Thread(null, new Solution(), "persefone", 1 << 28).start();
		// out.println((System.nanoTime() - startt));

	}

	@Override
	public void run() {
		solve(in.next());
		printf();
	}

	void solve(String s) {
		int n = s.length();
		int[][] dp = new int[n][n];
		boolean[][] isPal = new boolean[n + 1][n + 1];
		for (int i = 0; i < n; i++) {
			isPal[i][i] = true;
			dp[i][i] = 1;
			isPal[i + 1][i] = true;

		}
		
		for (int i = 2; i <= n; i++) {
			for (int j = 0; j <= n - i; j++) {
				isPal[j][j + i - 1] = isPal[j + 1][j + i - 2] & (s.charAt(j) == s.charAt(j + i - 1));
				dp[j][j + i - 1] = dp[j + 1][j + i - 1] + dp[j][j + i - 2] - dp[j + 1][j + i -2];
				if (isPal[j][i + j - 1]) dp[j][j + i - 1]++;
			}
		}
		
		for (int q = in.nextInt(); q > 0; q--) {
			add(dp[in.nextInt() - 1][in.nextInt() - 1], "\n");
		}
	}
	
	int lw(List<Integer> li, int k) {
		int l = 0, r = li.size(), R = r;
		while (l <= r) {
			int m = l + r >> 1;
			if (m == R) return m;
			if (li.get(m) >= k)
				r = m - 1;
			else
				l = m + 1;
		}
		return l;
	}

	int up(List<Integer> li, int k) {
		int l = 0, r = li.size(), R = r;
		while (l <= r) {
			int m = l + r >> 1;
			if (m == R) return m;
			if (li.get(m) > k)
				r = m - 1;
			else
				l = m + 1;
		}
		return l;
	}

	
	void computeHashArray(long[] hash, CharSequence s, int n) {
		for (int i = 1; i <= n; i++)
			hash[i] = (31 * hash[i - 1] + s.charAt(i - 1) - 'a') % MOD;
	}

	void computeModArray(long[] mod, int n) {
		mod[0] = 1;
		for (int i = 1; i <= n; i++)
			mod[i] = (mod[i - 1] * 31) % MOD;
	}

	long getHash(long[] hash, long[] mod, int i, int j) {
		return (hash[j] - hash[i] * mod[j - i]) % MOD;
	}

	long getHash(String s) {
		long hash = 0;
		for (int i = 0; i < s.length(); i++)
			hash = (hash * 31 + s.charAt(i) - 'a') % MOD;
		return hash;
	}

	void printf() {
		out.print(answer);
		out.close();
	}

	void printf(Stream<?> str) {
		str.forEach(o -> add(o, " "));
		add("\n");
	}

	void printf(Object... obj) {
		if (obj.getClass().isPrimitive()) {
			add(obj, "\n");
			return;
		}
		if (obj.length > 1) {
			printf(Arrays.stream(obj));
			return;
		}

		if (obj.length == 1) {
			Object o = obj[0];
			if (o instanceof int[])
				printf(Arrays.stream((int[]) o).boxed());
			else if (o instanceof char[])
				printf(String.valueOf(o).chars());
			else if (o instanceof long[])
				printf(Arrays.stream((long[]) o).boxed());
			else if (o instanceof double[])
				printf(Arrays.stream((double[]) o).boxed());
			else
				add(o, "\n");
		}
	}

	void printf(Collection<?> col) {
		printf(col.stream());
	}

	<T, K> void add(T t, K k) {
		if (t instanceof Collection<?>) {
			((Collection<?>) t).forEach(i -> add(i, " "));
		} else if (t instanceof Object[]) {
			Arrays.stream((Object[]) t).forEach(i -> add(i, " "));
		} else
			add(t);
		add(k);
	}

	<T> void add(T t) {
		answer.append(t);
	}

	static class Node {
		private String x, y;

		Node(String x, String y) {
			this.x = x;
			this.y = y;
		}

		@Override
		public boolean equals(Object o) {
			if (this == o)
				return true;
			if (o == null || !(o instanceof Node))
				return false;
			Node node = (Node) o;
			return x.equals(node.x) && y.equals(node.y);
		}

		@Override
		public int hashCode() {
			int hash = 31;
			hash = 89 * hash + x.hashCode();
			hash = 89 * hash + y.hashCode();
			return hash;
		}

		@Override
		public String toString() {
			return x + " " + y;
		}
	}

	static class Pair<K extends Comparable<? super K>, V extends Comparable<? super V>>
			implements Comparable<Pair<K, V>> {
		private K k;
		private V v;

		Pair() {
		}

		Pair(K k, V v) {
			this.k = k;
			this.v = v;
		}

		K getK() {
			return k;
		}

		V getV() {
			return v;
		}

		void setK(K k) {
			this.k = k;
		}

		void setV(V v) {
			this.v = v;
		}

		void setKV(K k, V v) {
			this.k = k;
			this.v = v;
		}

		@SuppressWarnings("unchecked")
		@Override
		public boolean equals(Object o) {
			if (this == o)
				return true;
			if (o == null || !(o instanceof Pair))
				return false;
			Pair<K, V> p = (Pair<K, V>) o;
			return k.compareTo(p.k) == 0 && v.compareTo(p.v) == 0;
		}

		@Override
		public int hashCode() {
			int hash = 31;
			hash = hash * 89 + k.hashCode();
			hash = hash * 89 + v.hashCode();
			return hash;
		}

		@Override
		public int compareTo(Pair<K, V> pair) {
			return k.compareTo(pair.k) == 0 ? v.compareTo(pair.v) : k.compareTo(pair.k);
		}

		@Override
		public Pair<K, V> clone() {
			return new Pair<K, V>(this.k, this.v);
		}

		@Override
		public String toString() {
			return String.valueOf(k).concat(" ").concat(String.valueOf(v)).concat("\n");
		}
	}

	static class Reader {
		private BufferedReader br;
		private StringTokenizer st;

		Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			try {
				while (st == null || !st.hasMoreTokens()) {
					st = new StringTokenizer(br.readLine());
				}
			} catch (IOException e) {
				e.printStackTrace();
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		int[] nextIntArray(int n) {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++)
				arr[i] = nextInt();
			return arr;
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		String nextLine() {
			String s = "";
			try {
				s = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return s;
		}
	}
}