Problem: Given the string S and m queries. The i-th query is given by the two strings xi and yi.

For each query, answer the longest substring of the string S, starting with xi and ending with yi.

For the string S, | S | represents the length of S. Also, the fact that the character string T is a substring of the character string S means that a certain integer i exists and Tj = Si + j is satisfied for 1 ≤ j ≤ | T |. Where Tj represents the jth character of T.

Constraints

* 1 ≤ | S | ≤ 2 x 105
* 1 ≤ m ≤ 105
* 1 ≤ | xi |, | yi |
* $ \ sum ^ m_ {i = 1} $ (| xi | + | yi |) ≤ 2 x 105
* S and xi, yi consist only of half-width lowercase letters.

Input

The input is given in the following format.


S
m
x1 y1
x2 y2
::
xm ym


* The character string S is given on the first line.
* The number of queries m is given in the second line.
* Of the m lines from the 3rd line, the i-th query string xi, yi is given on the i-th line, separated by spaces.

Output

Answer the maximum substring length in the following format.


len1
len2
::
lenm


Output the longest substring length leni that satisfies the condition for the i-th query on the i-th line of the m lines from the first line. If there is no such substring, output 0.

Examples

Input

abracadabra
5
ab a
a a
b c
ac ca
z z


Output

11
11
4
3
0


Input

howistheprogress
4
ist prog
s ss
how is
the progress


Output

9
12
5
11


Input

icpcsummertraining
9
mm m
icpc summer
train ing
summer mm
i c
i i
g g
train i
summer er


Output

2
10
8
0
4
16
1
6
6

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
//struct PMA {
//	PMA *next[128]; // next[0] is for fail
//	vector<int> accept;
//	PMA() { fill(next, next + 128, (PMA*)NULL); }
//};
//
//PMA *buildPMA(string p[1000], int size) {
//	PMA *root = new PMA;
//	for (int i = 0; i < size; i++) { // make trie
//		PMA *t = root;
//		for (int j = 0; p[i][j]; j++) {
//			int c = p[i][j];
//			if (t->next[c] == NULL) {
//				t->next[c] = new PMA;
//			}
//			t = t->next[c];
//		}
//		t->accept.push_back(i);
//	}
//	queue<PMA*> que; // make failure link using bfs
//	for (int c = 1; c < 128; c++) {
//		if (root->next[c]) {
//			root->next[c]->next[0] = root;
//			que.push(root->next[c]);
//		}
//		else {
//			root->next[c] = root;
//		}
//	}
//	while (!que.empty()) {
//		PMA *t = que.front();
//		que.pop();
//		for (int c = 1; c < 128; c++) {
//			if (t->next[c] != NULL) {
//				que.push(t->next[c]);
//				PMA *r = t->next[0];
//				while (!r->next[c]) {
//					r = r->next[0];
//				}
//				t->next[c]->next[0] = r->next[c];
//				for (vector<int>::iterator it = r->next[c]->accept.begin(); it != r->next[c]->accept.end(); it++) {
//					t->next[c]->accept.push_back(*it);
//				}
//			}
//		}
//	}
//	return root;
//}
//
//void deletePMA(PMA *root) {
//	set<PMA*> visit;
//	queue<PMA*> que;
//	que.push(root);
//	visit.insert(root);
//	while (!que.empty()) {
//		PMA *t = que.front();
//		que.pop();
//		for (int c = 1; c < 128; c++) {
//			if (t->next[c] == NULL) { continue; }
//			if (visit.count(t->next[c])) { continue; }
//			visit.insert(t->next[c]);
//			que.push(t->next[c]);
//		}
//	}
//	for (set<PMA*>::iterator it = visit.begin(); it != visit.end(); it++) {
//		delete *it;
//	}
//}
//
//// n = strlen(t)
//// m[i] = strlen(p[i])
//vector<int> match(const char *t, int n, const PMA *v, int m[], int size) {
//	vector<int> ret(size, -1);
//	//int n = strlen(t);
//	for (int i = 0; i < n; i++) {
//		int c = t[i];
//		while (!v->next[c]) {
//			v = v->next[0];
//		}
//		v = v->next[c];
//		for (vector<int>::const_iterator it = v->accept.begin(); it != v->accept.end(); it++) {
//			if (ret[*it] != -1) { continue; }
//			ret[*it] = i - m[*it] + 1;
//		}
//	}
//	return ret;
//}
//int main() {
//	while (1) {
//		int N, M, K; cin >> N >> M >> K;
//		vector<string>names;
//		char oks[1000][1000];
//		memset(oks, 0, sizeof(oks));
//		for (size_t i = 0; i < N; i++)
//		{
//
//			string from, to; cin >> from >> to;
//			auto ft = find(names.begin(), names.end(), from);
//			if (ft == names.end()) {
//				names.push_back(from);
//			}
//			auto tt = find(names.begin(), names.end(), to);
//			if (tt == names.end()) {
//				names.push_back(to);
//			}
//			ft = find(names.begin(), names.end(), from);
//			tt = find(names.begin(), names.end(), to);
//			oks[ft - names.begin()][tt - names.begin()] = true;
//		}
//		string seasons[1000];
//		int aa[3];
//		for (size_t i = 0; i < K; i++)
//		{
//			string st; cin >> st;
//			seasons[i] = st;
//			aa[i] = st.size();
//			
//		}
//		auto it = buildPMA(seasons, K);
//		char* c = "sakuraha";
//		vector<int>m(match(c, 9, it, aa, 3));
//		int a=0;
//		a++;
//	}
//	return 0;
//}

#define REP(i,n) for(int i=0;i<n;++i)

struct SuffixArray {
	struct SAComp {
		const int h; const vector<int> &g;
		SAComp(const int h_, const vector<int>&g_) : h(h_), g(g_) { ; }
		bool operator() (int a, int b) {
			return a == b ? false : g[a] != g[b] ? g[a] < g[b] : g[a + h] < g[b + h];
		}
	};

	static const int SIZE = 100000;
	int n;
	string str;
	vector<int> sa;
	vector<int> lcp;

	SuffixArray() { ; }
	SuffixArray(const string t):str(t) {
		Init();
	}
	void Init() {
		n = str.size();
		buildSA();
		buildLCP();
	}

	// O(mlogn)

	////?????°????????????
	//int find(const string p) {
	//	int m = p.size();
	//	int left = 0;
	//	int right = n-m;
	//	while (left < right) {
	//		int mid = (left + right) / 2;
	//		if (str.substr(sa[mid],m)<p.substr(0,m)) { left = mid + 1; }
	//		else { right = mid; }
	//	}
	//	return str.substr(sa[left], m)== p.substr(0, m)? sa[left] : -1;
	//}
private:
	//O(nlog^2n)
	void buildSA() {
		sa = vector<int>(n + 1);
		vector<int>g(n + 1);
		vector<int>b(n + 1);
		REP(i, n + 1) { sa[i] = i; g[i] = str[i]; }
		b[0] = 0;
		b[n] = 0;
		SAComp f(0, g);
		sort(sa.begin(), sa.end(),SAComp(0,g));
		for (int h = 1; b[n] != n; h *= 2) {
			SAComp comp(h, g);
			sort(sa.begin(), sa.end(), comp);
			REP(i, n) b[i + 1] = b[i] + comp(sa[i], sa[i + 1]);
			REP(i, n + 1) g[sa[i]] = b[i];
		}
	}
	void buildLCP() {
		lcp = vector<int>(n + 1);
		int h = 0;
		vector<int>b(n + 1);
		REP(i, n + 1) { b[sa[i]] = i; }
		REP(i, n + 1) {
			if (b[i]) {
				for (int j = sa[b[i] - 1]; j + h < n && i + h < n && str[j + h] == str[i + h]; h++) { ; }
				lcp[b[i]] = h;
			}
			else {
				lcp[b[i]] = -1;
			}
			if (h > 0) { h--; }
		}
	}
};

#define Seg_Max_N (1<<19) 
using Value = pair<int, int>;
Value dat[2 * Seg_Max_N];
struct segtree {
	int N;
	const Value ini=(make_pair(-1, 100000000));
	segtree() {}
	segtree(int n) {
		N = 1;
		while (N < n) N *= 2;
		for (int i = 0; i < 2 * N - 1; i++) {
			dat[i] = ini;
		}
	}
	// update k th element
	void update(int k, Value a) {
		k += N - 1; // leaf
		dat[k] = a;
		while (k > 0) {
			k = (k - 1) / 2;
			const Value al(dat[k * 2 + 1]);
			const Value ar(dat[k * 2 + 2]);
			dat[k] = make_pair(max(al.first,ar.first),min(al.second,ar.second));
		}
	}
	// min [a, b)
	Value  query(int a, int b) { return query(a, b, 0, 0, N); }
	Value  query(int a, int b, int k, int l, int r) {
		if (r <= a or b <= l) return ini;
		if (a <= l and r <= b) return dat[k];
		const int m = (l + r) / 2;
		const Value al(query(a, b, k * 2 + 1, l, m));
		const Value ar(query(a, b, k * 2 + 2, m, r));
		return make_pair(max(al.first, ar.first), min(al.second, ar.second));
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string st; cin >> st;
	SuffixArray sf(st.c_str());
	segtree seg(st.size() + 1);
	for (int i = 0; i < sf.n + 1; ++i) {
		seg.update(i, make_pair(sf.sa[i], sf.sa[i]));
	}
	int M; cin >> M;
	for (int i = 0; i < M; ++i) {
		{
			int f, t;
			string from; cin >> from;
			{
				int left, right;
				{
					int amin = -1;
					int amax = sf.n+1;
					int a = 31;
					while (a--) {
						int amid = (amin + amax) / 2;
						string ast = sf.str.substr(sf.sa[amid], from.size());
						if (ast < from)amin = amid;
						else amax = amid;
					}
					left = amin;
				}
				{
					int amin = -1;
					int amax = sf.n + 1;
					int a = 31;
					while (a--) {
						int amid = (amin + amax) / 2; 
						string ast = sf.str.substr(sf.sa[amid], from.size());
						if (ast <= from)amin = amid;
						else amax = amid;
					}
					right = amin;
				}
				f = seg.query(left+1 , right+1 ).second;
			}
			int ans = 0;
			
			string to; cin >> to;
			{
			
				ans += to.size();
				int left, right;
				{
					int amin = -1;
					int amax = sf.n + 1;
					int a = 31;
					while (a--) {
						int amid = (amin + amax) / 2;
						string ast = sf.str.substr(sf.sa[amid], to.size());
						if (ast < to)amin = amid;
						else amax = amid;
					}
					left = amin;
				}
				{
					int amin = -1;
					int amax = sf.n + 1;
					int a = 31;
					while (a--) {
						int amid = (amin + amax) / 2;
						string ast = sf.str.substr(sf.sa[amid], to.size());
						if (ast <= to)amin = amid;
						else amax = amid;
					}
					right = amin;
				}
				t = seg.query(left+1, right+1).first;
			}
			 ans+= t - f;
			 if (ans < 0)ans = -1;
			 if (ans < to.size())ans = -1;
			 if (ans < from.size())ans = -1;
			 if (t == -1 || f > 1000000)ans = -1;
			 if (ans == -1)ans = 0;
			 printf("%d\n", ans);
		}
	}
	return 0;
}