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.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.HashMap;
import java.util.List;
import java.util.Map;
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 t) {
		int n = t.length();
		List<Map<String, List<Integer>>> li = new ArrayList<>();
		for (int i = 1; i < 5; i++) {
			Map<String, List<Integer>> map = new HashMap<>();
			for (int j = 0; j + i <= n; j++)
				map.computeIfAbsent(t.substring(j, j + i), v -> new ArrayList<>()).add(j);
			li.add(map);
		}

		int q = in.nextInt();
		Map<Node, Integer> map = new HashMap<>();
		for (; q > 0; q--) {
			String s = in.next();
			String w = in.next();
			Node node = new Node(s, w);
			if (map.containsKey(node)) {
				add(map.get(node), "\n");
				continue;
			}
			List<Integer> ls = li.get(s.length() - 1).get(s);
			List<Integer> lw = li.get(w.length() - 1).get(w);

			if (ls == null || lw == null || ls.isEmpty() || lw.isEmpty()) {
				add(-1, "\n");
				continue;
			}
			if (s.contains(w) || w.contains(s)) {
				int l = Math.max(s.length(), w.length());
				map.put(node, l);
				add(l, "\n");
				continue;
			}

			if (ls.size() >= 10 * lw.size()) {
				int l = find(lw, ls, w.length(), s.length());
				map.put(node, l);
				add(l, "\n");
				continue;
			}

			if (lw.size() >= 10 * ls.size()) {
				int l = find(ls, lw, s.length(), w.length());
				map.put(node, l);
				add(l, "\n");
				continue;
			}

			List<Integer> ll = new ArrayList<>();
			int i = 0, j = 0, count = 0;
			int lasts = -1, lastw = -1, min = Integer.MAX_VALUE;
			while (i < ls.size() && j < lw.size()) {
				count++;
				int x = ls.get(i);
				int y = lw.get(j);
				boolean check = true;
				if (x < y) {
					i++;
					ll.add(x);
					lasts = x;
				} else {
					j++;
					ll.add(y);
					lastw = y;
					check = false;
				}
				if (count > 1) {
					if (check && lastw != -1)
						min = Math.min(min, x + s.length() - lastw);
					if (!check && lasts != -1)
						min = Math.min(min, y + w.length() - lasts);
				}

			}

			if (i < ls.size()) {
				min = Math.min(min, ls.get(i) + s.length() - lastw);
			}
			if (j < lw.size()) {
				min = Math.min(min, lw.get(j) + w.length() - lasts);
			}
			map.put(node, min);
			add(min, "\n");
		}

	}

	int find(List<Integer> ls, List<Integer> lw, int a, int b) {
		int s = ls.size(), w = lw.size();
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < s; i++) {
			int pos = lw(lw, 0, w, ls.get(i));
			if (pos == w) {
				min = Math.min(min, ls.get(i) + a - lw.get(w - 1));
				return min;
			} else if (pos == 0) {
				min = Math.min(min, lw.get(0) + b - ls.get(i));
			} else {
				int min1 = Math.min(ls.get(i) + a - lw.get(pos - 1), lw.get(pos) + b - ls.get(i));
				min = Math.min(min, min1);
			}
		}
		return min;
	}

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

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

	void computeHashArray(long[] hash, String 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;
		}
	}
}