DZY loves strings, and he enjoys collecting them.

In China, many people like to use strings containing their names' initials, for example: xyz, jcvb, dzy, dyh.

Once DZY found a lucky string s. A lot of pairs of good friends came to DZY when they heard about the news. The first member of the i-th pair has name ai, the second one has name bi. Each pair wondered if there is a substring of the lucky string containing both of their names. If so, they want to find the one with minimum length, which can give them good luck and make their friendship last forever.

Please help DZY for each pair find the minimum length of the substring of s that contains both ai and bi, or point out that such substring doesn't exist.

A substring of s is a string slsl + 1... sr for some integers l, r (1 ≤ l ≤ r ≤ |s|). The length of such the substring is (r - l + 1).

A string p contains some another string q if there is a substring of p equal to q.

Input

The first line contains a string s (1 ≤ |s| ≤ 50000).

The second line contains a non-negative integer q (0 ≤ q ≤ 100000) — the number of pairs. Each of the next q lines describes a pair, the line contains two space-separated strings ai and bi (1 ≤ |ai|, |bi| ≤ 4).

It is guaranteed that all the strings only consist of lowercase English letters.

Output

For each pair, print a line containing a single integer — the minimum length of the required substring. If there is no such substring, output -1.

Examples

Input

xudyhduxyz
3
xyz xyz
dyh xyz
dzy xyz


Output

3
8
-1


Input

abcabd
3
a c
ab abc
ab d


Output

2
3
3


Input

baabcabaaa
2
abca baa
aa aba


Output

6
4

Note

The shortest substrings in the first sample are: xyz, dyhduxyz.

The shortest substrings in the second sample are: ca, abc and abd.

The shortest substrings in the third sample are: baabca and abaa.
import java.util.List;
import java.io.IOException;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.util.HashMap;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Collections;
import java.io.InputStream;

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

class TaskD {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        char[] S = in.nextString().toCharArray();
//        StringBuilder stringBuilder = new StringBuilder();
//        for (int i = 0; i < 100000; i++) {
//            stringBuilder.append((char) (new Random().nextInt(26) + 'a'));
//        }
//        char[] S = stringBuilder.toString().toCharArray();
        int N = S.length;

        HashMap<Integer, Integer> idx = new HashMap<Integer, Integer>();
        HashMap<Long, Integer> cachedAns = new HashMap<Long, Integer>();
        ArrayList<Integer>[] f = new ArrayList[N * 4];
        for (int i = 0; i < N * 4; i++) {
            f[i] = new ArrayList<Integer>();
        }

        int crtIdx = 0;
        for (int i = 0; i < N; i++) {
            int s = 0;
            for (int j = 0; j < 4 && i + j < N; j++) {
                s = s * 26 + S[i + j] - 'a' + 1;
                int p;
                if (!idx.containsKey(s)) {
                    p = crtIdx;
                    idx.put(s, crtIdx++);
                }
                else {
                    p = idx.get(s);
                }

                f[p].add(i);
            }
        }

        int T = 500;
        int Q = in.nextInt();
        while(Q-- > 0) {
            char[] a = in.nextString().toCharArray();
            char[] b = in.nextString().toCharArray();
            int ha = getHash(a);
            int hb = getHash(b);
            int lenA = a.length;
            int lenB = b.length;

            int idxA = -1;
            if (idx.containsKey(ha)) {
                idxA = idx.get(ha);
            }
            int idxB = -1;
            if (idx.containsKey(hb)) {
                idxB = idx.get(hb);
            }

            if (idxA == -1 || idxB == -1) {
                out.println(-1);
                continue;
            }

            if (f[idxA].size() > f[idxB].size()) {
                int aux = idxA; idxA = idxB; idxB = aux;
                aux = lenA; lenA = lenB; lenB = aux;
            }
            int ans;
            long key = idxA + (long) (f.length + 1) * idxB;
            if (cachedAns.containsKey(key)) {
                ans = cachedAns.get(key);
                out.println(ans);
                continue;
            }

            if (f[idxB].size() <= T) {
                ans = goMerge(f[idxA], lenA, f[idxB], lenB);
            }
            else {
                ans = goFullSearch(f[idxA], lenA, f[idxB], lenB);
            }

            cachedAns.put(key, ans);
            out.println(ans);
        }
    }

    private int goFullSearch(ArrayList<Integer> A, int lenA, ArrayList<Integer> B, int lenB) {
        int ret = Integer.MAX_VALUE;
        for (int a : A) {
            int pos = Collections.binarySearch(B, a);
            if (pos < 0) {
                pos = -pos - 1;
            }
            if (pos < B.size()) {
                ret = Math.min(ret, calc(a, a + lenA - 1, B.get(pos), B.get(pos) + lenB - 1));
            }
            if (pos > 0) {
                ret = Math.min(ret, calc(a, a + lenA - 1, B.get(pos - 1), B.get(pos - 1) + lenB - 1));
            }
        }

        if (ret == Integer.MAX_VALUE) {
            ret = -1;
        }
        return ret;
    }

    private int goMerge(ArrayList<Integer> A, int lenA, ArrayList<Integer> B, int lenB) {
        int N = A.size();
        int M = B.size();
        int i = 0;
        int j = 0;
        int ret = Integer.MAX_VALUE;
        int lasti = -1;
        int lastj = -1;

        while (i < N && j < M) {
            if (A.get(i) < B.get(j)) {
                if (lastj != -1) {
                    ret = Math.min(ret, calc(A.get(i), A.get(i) + lenA - 1, lastj, lastj + lenB - 1));
                }
                lasti = A.get(i);
                i++;
            }
            else {
                if (lasti != -1) {
                    ret = Math.min(ret, calc(B.get(j), B.get(j) + lenB - 1, lasti, lasti + lenA - 1));
                }
                lastj = B.get(j);
                j++;
            }
        }
        if (i < N) {
            if (lastj == -1) {
                throw new RuntimeException();
            }
            ret = Math.min(ret, calc(A.get(i), A.get(i) + lenA - 1, lastj, lastj + lenB - 1));
        }
        if (j < M) {
            if (lasti == -1) {
                throw new RuntimeException();
            }
            ret = Math.min(ret, calc(B.get(j), B.get(j) + lenB - 1, lasti, lasti + lenA - 1));
        }

        if (ret == Integer.MAX_VALUE) {
            ret = -1;
        }
        return ret;
    }

    private int calc(int a1, int b1, int a2, int b2) {
        int left = Math.min(a1, a2);
        int right = Math.max(b1, b2);
        return right - left + 1;
    }

    private int getHash(char[] s) {
        int ret = 0;
        for (int i = 0; i < s.length; i++) {
            ret = ret * 26 + s[i] - 'a' + 1;
        }
        return ret;
    }
}

class InputReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

    public String nextString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuffer res = new StringBuffer();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));

        return res.toString();
    }

    private boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

}

