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>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

typedef vector<int> SuffixArray;
int n, k;
vi rnk, tmp;

bool comp_sa(const int i, const int j)
{
	if (rnk[i] != rnk[j]) return rnk[i] < rnk[j];
	else
	{
		int ri = i + k <= n ? rnk[i + k] : -1;
		int rj = j + k <= n ? rnk[j + k] : -1;
		return ri < rj;
	}
}

SuffixArray construct_sa(const string& s)
{
	n = s.size();
	SuffixArray sa(n + 1);
	rnk.resize(n + 1), tmp.resize(n + 1);
	REP(i, n + 1)
	{
		sa[i] = i;
		if (i == n) rnk[i] = -1;
		else rnk[i] = s[i];
	}
	for (k = 1; k <= n; k *= 2)
	{
		sort(ALL(sa), comp_sa);
		tmp[sa[0]] = 0;
		REP(i, n) tmp[sa[i + 1]] = tmp[sa[i]] + (comp_sa(sa[i], sa[i + 1]) ? 1 : 0);
		rnk = tmp;
	}
	return sa;
}

bool search(const string& s, const string& t, const SuffixArray& sa)
{
	int l = 0, r = s.size();
	while (r - l > 1) 
	{
		int mid = (r + l) / 2;
		if (s.compare(sa[mid], t.size(), t) < 0) l = mid;
		else r = mid;
	}
	return s.compare(sa[r], t.size(), t) == 0;
}

int lower_bound(const string& s, const string& t, const SuffixArray& sa)
{
	int l = 0, r = s.size() + 1;
	while (r - l > 1)
	{
		int mid = (r + l) / 2;
		if (s.compare(sa[mid], t.size(), t) < 0) l = mid;
		else r = mid;
	}
	return r;
}

int upper_bound(const string& s, const string& t, const SuffixArray& sa)
{
	int l = 0, r = s.size() + 1;
	while (r - l > 1)
	{
		int mid = (r + l) / 2;
		if (s.compare(sa[mid], t.size(), t) <= 0) l = mid;
		else r = mid;
	}
	return r;
}
struct Data
{
	int num;
	Data() :num(INF) {};
	Data(int n) :num(n) {};
};
struct SegmentTree
{
	int n; vector<Data> data;
	SegmentTree(int N)
	{
		n = 1;
		while (n < N) n *= 2;
		data.resize(2 * n);
	}
private:
	Data sub(int left, int right, int node, int nleft, int nright)
	{
		if (nright <= left || right <= nleft) return Data();
		if (left <= nleft && nright <= right) return data[node];
		Data vl = sub(left, right, node * 2 + 1, nleft, (nleft + nright) / 2);
		Data vr = sub(left, right, node * 2 + 2, (nleft + nright) / 2, nright);
		return min(vl.num, vr.num);
	}

public:
	void update(int pos, Data value)
	{
		pos += n - 1;
		data[pos] = value;
		while (pos > 0)
		{
			pos = (pos - 1) / 2;
			data[pos] = min(data[pos * 2 + 1].num, data[pos * 2 + 2].num);
		}
	}
	Data min_query(int left, int right)
	{
		return sub(left, right, 0, 0, n);
	}
};


struct Data2
{
	int num;
	Data2() :num(-1) {};
	Data2(int n) :num(n) {};
};

struct SegmentTree2
{
	int n; vector<Data2> data2;
	SegmentTree2(int N)
	{
		n = 1;
		while (n < N) n *= 2;
		data2.resize(2 * n);
	}
private:
	Data2 sub(int left, int right, int node, int nleft, int nright)
	{
		if (nright <= left || right <= nleft) return Data2();
		if (left <= nleft && nright <= right) return data2[node];
		Data2 vl = sub(left, right, node * 2 + 1, nleft, (nleft + nright) / 2);
		Data2 vr = sub(left, right, node * 2 + 2, (nleft + nright) / 2, nright);
		return max(vl.num, vr.num);
	}

public:
	void update(int pos, Data2 value)
	{
		pos += n - 1;
		data2[pos] = value;
		while (pos > 0)
		{
			pos = (pos - 1) / 2;
			data2[pos] = max(data2[pos * 2 + 1].num, data2[pos * 2 + 2].num);
		}
	}
	Data2 max_query(int left, int right)
	{
		return sub(left, right, 0, 0, n);
	}
};

int main()
{
	string s; int m;
	cin >> s >> m;
	SuffixArray sa = construct_sa(s);
	int n = sa.size();
	SegmentTree minst(n);
	SegmentTree2 maxst(n);
	REP(i, n)
	{
		minst.update(i, sa[i]);
		maxst.update(i, sa[i]);
	}
	REP(i, m)
	{
		string x, y; cin >> x >> y;
		if (search(s, x, sa) && search(s, y, sa))
		{
			int lx = lower_bound(s, x, sa);
			int rx = upper_bound(s, x, sa);
			int ly = lower_bound(s, y, sa);
			int ry = upper_bound(s, y, sa);
			int l = minst.min_query(lx, rx).num;
			int r = maxst.max_query(ly, ry).num;
			if (l + x.size() > r + y.size()) puts("0");
			else cout << r - l + (int)y.size() << endl;
		}
		else puts("0");
	}
	return 0;
}