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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

int T_length,P_length,range;
int *Rank;
int *Suffix_Array;
int *Work;

char *T,*P;

enum Type{
	Big,
	Small,
};

struct RMQ{
	void set(int arg_minimum,int arg_maximum){
		minimum = arg_minimum;
		maximum = arg_maximum;
	}
	int minimum,maximum;
};

int N = 1;
RMQ* Tree;

void init(int first_N){
	while(N < first_N)N <<= 1;
}

void update(int index, int value){

	index += N-1;

	Tree[index].minimum = min(Tree[index].minimum,value);
	Tree[index].maximum = max(Tree[index].maximum,value);

	index = (index-1)/2;

	while(true){

		Tree[index].minimum = min(Tree[2*index+1].minimum,Tree[2*index+2].minimum);
		Tree[index].maximum = max(Tree[2*index+1].maximum,Tree[2*index+2].maximum);

		if(index == 0)break;
		else{
			index = (index-1)/2;
		}
	}
}


ll find(int search_left,int search_right,int node_id,int node_left,int node_right,Type type){

	if(search_right < node_left || search_left > node_right){
		if(type == Small){
			return BIG_NUM;
		}else{ //type == Big
			return -1;
		}
	}

	if(search_left <= node_left && search_right >= node_right){
		if(type == Small){
			return Tree[node_id].minimum;
		}else{
			return Tree[node_id].maximum;
		}
	}

	if(type == Small){
		ll left_min = find(search_left,search_right,2*node_id+1,node_left,(node_left+node_right)/2,type);
		ll right_min = find(search_left,search_right,2*node_id+2,(node_left+node_right)/2+1,node_right,type);

		return min(left_min,right_min);
	}else{ //type == Big
		ll left_max = find(search_left,search_right,2*node_id+1,node_left,(node_left+node_right)/2,type);
		ll right_max = find(search_left,search_right,2*node_id+2,(node_left+node_right)/2+1,node_right,type);

		return max(left_max,right_max);
	}
}

int strCmp_Suffix_Array(int start){
	int index,ret;

	ret = 0;

	for(index = 0; index < P_length && T[start+index] != '\0'; index++){
		if(P[index] != T[start+index]){
			if(P[index] > T[start+index]){
				ret = 2;
			}else{
				ret = 1;
			}
			break;
		}
	}
	if(ret == 0 && index < P_length){
		ret = 2;
	}
	return ret;
}

int find_match_left(){

	int ret = BIG_NUM;

	int left = 0,right = T_length,m;
	m = (left+right)/2;

	while(left <= right){
		switch(strCmp_Suffix_Array(Suffix_Array[m])){
		case 0:
			ret = min(ret,m);
			right = m-1;
			break;
		case 1:
			right = m-1;
			break;
		case 2:
			left = m+1;
			break;
		}
		m = (left+right)/2;
	}
	return ret;
}

int find_match_right(){

	int ret = -1;

	int left = 0,right = T_length,m;
	m = (left+right)/2;

	while(left <= right){
		switch(strCmp_Suffix_Array(Suffix_Array[m])){
		case 0:
			ret = max(ret,m);
			left = m+1;
			break;
		case 1:
			right = m-1;
			break;
		case 2:
			left = m+1;
			break;
		}
		m = (left+right)/2;
	}
	return ret;
}


bool compare_Suffix_Array(int a,int b){
	if(Rank[a] != Rank[b])return Rank[a] < Rank[b];
	else{
		int rank_a = a + range <= T_length ? Rank[a+range]:-1;
		int rank_b = b + range <= T_length ? Rank[b+range]:-1;
		return rank_a < rank_b;
	}
}

void make_Suffix_Array(){
	for(int i = 0; i <= T_length; i++){
		Suffix_Array[i] = i;
		Rank[i] = i < T_length? T[i]:-1;
	}

	for(range = 1; range <= T_length; range*=2){
		sort(Suffix_Array,Suffix_Array+(T_length+1),compare_Suffix_Array);

		Work[Suffix_Array[0]] = 0;
		for(int i = 1; i <= T_length; i++){
			Work[Suffix_Array[i]] = Work[Suffix_Array[i-1]] + (compare_Suffix_Array(Suffix_Array[i-1],Suffix_Array[i])?1:0);
		}
		for(int i = 0; i <= T_length; i++){
			Rank[i] = Work[i];
		}
	}
}


int main(){

	T = new char[2000001];
	scanf("%s",T);

	for(T_length = 0; T[T_length] != '\0'; T_length++);
	Rank = new int[T_length+1];
	Suffix_Array = new int[T_length+1];
	Work = new int[T_length+1];

	make_Suffix_Array();

	init(T_length);

	Tree = (RMQ*)malloc(sizeof(RMQ)*(2*N));

	for(int i = 0; i <= 2*N-2; i++){
		Tree[i].set(BIG_NUM,-1);
	}

	for(int i = 0; i <= T_length; i++){
		update(i,Suffix_Array[i]);
	}

	P = new char[2000001];

	int M,match_left,match_right,most_left_index,most_right_index,first_P_length;

	scanf("%d",&M);

	for(int loop = 0; loop < M; loop++){

		scanf("%s",P);
		for(P_length = 0;P[P_length] != '\0';P_length++);
		first_P_length = P_length;

		match_left = find_match_left();
		match_right = find_match_right();

		if(match_left != BIG_NUM){
			most_left_index = find(match_left,match_right,0,0,N-1,Small);
		}

		scanf("%s",P);
		for(P_length = 0;P[P_length] != '\0';P_length++);

		if(match_left == BIG_NUM){
			printf("0\n");
			continue;
		}

		match_left = find_match_left();
		match_right = find_match_right();

		if(match_left != BIG_NUM){
			most_right_index = find(match_left,match_right,0,0,N-1,Big);
			most_right_index = most_right_index+P_length-1;
		}else{
			printf("0\n");
			continue;
		}

		if(most_left_index > most_right_index || most_left_index+first_P_length-1 > most_right_index){
			printf("0\n");
		}else{
			printf("%d\n",most_right_index-most_left_index+1);
		}
	}

	return 0;
}