// Arup Guha
// 4/9/2013
// Solution to 2013 Chicago Contest Problem C: Automatic Trading

/* This solution uses an efficient algorithm to calculate the longest common prefix,
 * via a suffix array. */

import java.util.*;

public class c {


	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		String input = stdin.next();

		// Go through all cases.
		while (!input.equals("*")) {

			// First calculate the suffix array.
			int[][] sArray = getSuffixArray(input);

			// Find the longest common prefix length.
			int n = stdin.nextInt();
			for (int i=0; i<n; i++) {
				int index1 = stdin.nextInt();
				int index2 = stdin.nextInt();
				System.out.println(lcp(sArray, index1, index2));
			}

			input = stdin.next();
		}
	}

	// Returns the first power of 2 greater than or equal to n.
	public static int getIter(int n) {
		int cnt = 1, ans = 1;
		while (cnt < n) {
			ans++;
			cnt = 2*cnt;
		}
		return ans;
	}

	public static int[][] getSuffixArray(String s) {

		int n = s.length();
		int[][] ans = new int[getIter(n)][n];

		ans[0] = getInitPos(s);
		int cnt = 1, iter = 0;

		while (cnt < n) {

			// Create pairs of values.
			pair[] temp = new pair[n];
			for (int i=0; i<n; i++) {
				if (i+cnt < n)
					temp[i] = new pair(i, ans[iter][i], ans[iter][i+cnt]);
				else
					temp[i] = new pair(i, ans[iter][i]);
			}

			// Sort these.
			Arrays.sort(temp);
			int[] newRanks = new int[n];
			int newCnt = 0;
			newRanks[0] = 0;
			for (int i=1; i<n; i++) {
				if (temp[i].equals(temp[i-1]))
					newRanks[i] = newRanks[i-1];
				else
					newRanks[i] = newRanks[i-1] + 1;
			}

			iter++;

			// Copy in new rankings of prefixes of length 2*cnt
			for (int i=0; i<n; i++)
				ans[iter][temp[i].index] = newRanks[i];

			// Go to the next power of two!
			cnt = cnt*2;
		}

		return ans;
	}

	public static int[] getInitPos(String s) {

		boolean[] used = new boolean[256];

		// Find each unique character in the string.
		for (int i=0; i<s.length(); i++)
			if (!used[s.charAt(i)])
				used[s.charAt(i)] = true;

		// Create list of all characters in the string.
		HashMap<Character,Integer> map = new HashMap<Character,Integer>();
		int cnt = 0;
		for (int i=0; i<used.length; i++) {
			if (used[i]) {
				map.put((char)(i), cnt);
				cnt++;
			}
		}

		// For each character in string s, its unique identifier is stored.
		int[] pos = new int[s.length()];
		for (int i=0; i<pos.length; i++)
			pos[i] = map.get(s.charAt(i));

		return pos;
	}

	// Returns the length of the longest common prefix of the string[x..] and string[y..]
	// given that sArray stores the suffix array of string. In particular, sArray[i] stores
	// the suffix array for strings of length 2^i.
	public static int lcp(int[][] sArray, int x, int y) {

		int k, ret = 0, n = sArray[0].length;
		if (x == y)
			return n - x;

		// Go through and find each matching substring of length perfect power of 2
		// and iteratively try to "grow" the matching substrings.
		for (k = sArray.length - 2; k >= 0 && x < n && y < n; k --) {

			// These 2^k characters match, update answer and try to match what's left.
			if (sArray[k][x] == sArray[k][y]) {
				x += 1 << k;
				y += 1 << k;
				ret += 1 << k;
			}
		}

		return ret;
	}

}

class pair implements Comparable<pair> {

	public int index;
	public int first;
	public int second;

	// Pre-cond: a >= 0, b >=0
	public pair(int i, int a, int b) {
		index = i;
		first = a;
		second = b;
	}

	// Ensures any "pair" with just a comes before any pair with a and something else.
	public pair(int i, int a) {
		index = i;
		first = a;
		second = -1;
	}

	public int compareTo(pair other) {
		if (first != other.first)
			return first - other.first;
		return second - other.second;
	}

	public boolean equals(pair other) {
		return first == other.first && second == other.second;
	}
}