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
#include <bits/stdc++.h>
using namespace std;
int T_char_count[128] = {0}, P_char_count[128];
class LocRecord {
 public:
  LocRecord() {
    locationTable = new int*[128];
    for (int i = 48; i <= 57; i++) {
      if (T_char_count[i] > 0) {
        locationTable[i] = new int[T_char_count[i] + 1];
      }
    }
    for (int i = 65; i <= 90; i++) {
      if (T_char_count[i] > 0) {
        locationTable[i] = new int[T_char_count[i] + 1];
      }
    }
    for (int i = 97; i <= 122; i++) {
      if (T_char_count[i] > 0) {
        locationTable[i] = new int[T_char_count[i] + 1];
      }
    }
  }
  void init() {
    int limit;
    for (int i = 48; i <= 57; i++) {
      limit = T_char_count[i];
      if (T_char_count[i] > 0) {
        index[i] = 0;
        for (int k = 0; k <= limit; k++) {
          locationTable[i][k] = -1;
        }
      }
    }
    for (int i = 65; i <= 90; i++) {
      limit = T_char_count[i];
      if (T_char_count[i] > 0) {
        index[i] = 0;
        for (int k = 0; k <= limit; k++) {
          locationTable[i][k] = -1;
        }
      }
    }
    for (int i = 97; i <= 122; i++) {
      limit = T_char_count[i];
      if (T_char_count[i] > 0) {
        index[i] = 0;
        for (int k = 0; k <= limit; k++) {
          locationTable[i][k] = -1;
        }
      }
    }
  }
  void init_index() {
    for (int i = 48; i <= 57; i++) {
      index[i] = 0;
    }
    for (int i = 65; i <= 90; i++) {
      index[i] = 0;
    }
    for (int i = 97; i <= 122; i++) {
      index[i] = 0;
    }
  }
  void regist_loc(int ch, int location) {
    locationTable[ch][index[ch]] = location;
    index[ch]++;
  }
  int next_loc(int ch) {
    int ret = locationTable[ch][index[ch]];
    index[ch]++;
    return ret;
  }

 private:
  int** locationTable;
  int index[128];
};
void compress(int compressed_array[], char base_array[], int& compressed_length,
              bool T_FLG) {
  int comp_index = 0, count = 0;
  char ch = base_array[0];
  for (int i = 0; base_array[i] != '\0';) {
    if (ch == base_array[i]) {
      if (T_FLG) {
        T_char_count[ch]++;
      } else {
        P_char_count[ch]++;
      }
      count++;
      if (base_array[i + 1] == '\0') {
        if (count >= 4) {
          compressed_array[comp_index - 2] = -1;
          compressed_array[comp_index - 1] = count;
        } else {
          compressed_array[comp_index++] = ch;
        }
      } else {
        if (count <= 3) {
          compressed_array[comp_index++] = ch;
        }
      }
      i++;
    } else {
      if (count >= 4) {
        compressed_array[comp_index - 2] = -1;
        compressed_array[comp_index - 1] = count;
      }
      count = 0;
      ch = base_array[i];
    }
  }
  compressed_length = comp_index;
}
int main() {
  int T_comp_index, P_comp_index, comp_P_length, comp_T_length, tmp, div_tmp;
  char* T = new char[100001];
  int* compressedT = new int[100001];
  char P[100001];
  int compressedP[100001];
  scanf("%s", T);
  compress(compressedT, T, comp_T_length, true);
  LocRecord loc_record;
  loc_record.init();
  loc_record.regist_loc(compressedT[0], 0);
  for (int i = 1; i < comp_T_length; i++) {
    if (compressedT[i] != -1 && compressedT[i - 1] != -1) {
      loc_record.regist_loc(compressedT[i], i);
    }
  }
  int* total_count = new int[comp_T_length];
  int sum = 0;
  for (int i = 0; i < comp_T_length; i++) {
    if ((i > 0 && compressedT[i - 1] != -1 && compressedT[i] != -1) || i == 0) {
      total_count[i] = sum;
      sum++;
    } else if (i > 0 && compressedT[i - 1] == -1) {
      sum += (compressedT[i] - 2);
      total_count[i] = sum;
      sum++;
    }
  }
  int n, left_start, right_end, left_length, right_length;
  bool zeroFLG, foundFLG;
  scanf("%d", &n);
  for (int loop_number = 0; loop_number < n; loop_number++) {
    left_start = -1, right_end = -1;
    for (int inner = 0; inner < 2; inner++) {
      zeroFLG = false;
      foundFLG = false;
      scanf("%s", P);
      if (inner == 0) {
        for (left_length = 0; P[left_length] != '\0'; left_length++)
          ;
      } else {
        for (right_length = 0; P[right_length] != '\0'; right_length++)
          ;
      }
      for (int i = 0; i < 128; i++) P_char_count[i] = 0;
      compress(compressedP, P, comp_P_length, false);
      for (int i = 0; i < 128; i++) {
        if (T_char_count[i] < P_char_count[i]) {
          zeroFLG = true;
          break;
        }
      }
      if (zeroFLG) break;
      bool multFLG = false, leftsuceedFLG = false, rightsucceedFLG = false;
      int most_left = compressedP[0], most_right = compressedP[0];
      for (int i = 1; i < comp_P_length; i++) {
        if (compressedP[i - 1] != -1 && compressedP[i] != -1) {
          most_right = compressedP[i];
          if (compressedP[i] != most_left) {
            multFLG = true;
          }
        }
      }
      if (comp_P_length > 2 && compressedP[comp_P_length - 2] == -1) {
        rightsucceedFLG = true;
      }
      if (comp_P_length > 1 && compressedP[1] == -1) leftsuceedFLG = true;
      if (multFLG) {
        loc_record.init_index();
        T_comp_index = loc_record.next_loc(most_right);
        if (T_comp_index == -1) {
          break;
        }
        int outputFLG;
        while (T_comp_index < comp_T_length) {
          tmp = T_comp_index;
          P_comp_index = comp_P_length - 1;
          outputFLG = 0;
          while (P_comp_index >= 0 && tmp >= 0) {
            if (tmp == T_comp_index) {
              if (rightsucceedFLG) {
                if ((tmp < comp_T_length - 2) && (compressedT[tmp + 1] == -1) &&
                    (compressedT[tmp + 2] >= compressedP[comp_P_length - 1])) {
                  tmp -= 1;
                  P_comp_index -= 3;
                } else {
                  break;
                }
              } else {
                if ((tmp < comp_T_length - 2) && (compressedT[tmp + 1] == -1)) {
                  if (compressedP[P_comp_index] !=
                      compressedP[P_comp_index - 1]) {
                    tmp--;
                    P_comp_index--;
                  } else if ((compressedP[P_comp_index] ==
                              compressedP[P_comp_index - 1]) &&
                             (compressedP[P_comp_index - 1] !=
                              compressedP[P_comp_index - 2])) {
                    tmp--;
                    P_comp_index -= 2;
                  } else {
                    tmp--;
                    P_comp_index -= 3;
                  }
                } else {
                  tmp--;
                  P_comp_index--;
                }
              }
            } else if (leftsuceedFLG && P_comp_index == 2) {
              if ((tmp > 1) && (compressedT[tmp - 1] == -1) &&
                  (compressedT[tmp] >= compressedP[P_comp_index]) &&
                  compressedT[tmp - 2] == compressedP[0]) {
                tmp -= 3;
                P_comp_index -= 3;
                outputFLG = 2;
              } else {
                break;
              }
            } else if ((leftsuceedFLG == false) && (P_comp_index == 2) &&
                       (compressedP[2] == compressedP[1]) &&
                       (compressedP[1] == compressedP[0])) {
              if ((tmp >= 2) && (compressedT[tmp - 1] == -1) &&
                  (compressedT[tmp - 2] == compressedP[0])) {
                tmp -= 3;
                P_comp_index -= 3;
                outputFLG = 3;
              } else if (compressedP[P_comp_index] == compressedT[tmp] &&
                         tmp > 1 && compressedT[tmp] == compressedT[tmp - 1] &&
                         compressedT[tmp - 1] == compressedT[tmp - 2]) {
                tmp -= 3;
                P_comp_index -= 3;
              } else {
                break;
              }
            } else if ((leftsuceedFLG == false) && (P_comp_index == 1) &&
                       (compressedP[1] == compressedP[0])) {
              if ((tmp >= 2) && (compressedT[tmp - 1] == -1) &&
                  (compressedT[tmp - 2] == compressedP[0])) {
                tmp -= 3;
                P_comp_index -= 2;
                outputFLG = 3;
              } else if ((compressedP[P_comp_index] == compressedT[tmp]) &&
                         (tmp > 0) && (compressedT[tmp - 1] != -1) &&
                         (compressedT[tmp - 2] != -1) &&
                         (compressedT[tmp] == compressedT[tmp - 1])) {
                tmp -= 2;
                P_comp_index -= 2;
              } else if ((compressedP[P_comp_index] == compressedT[tmp]) &&
                         (tmp == 1) &&
                         (compressedT[tmp] == compressedT[tmp - 1])) {
                tmp -= 2;
                P_comp_index -= 2;
              } else {
                break;
              }
            } else if ((leftsuceedFLG == false) && (P_comp_index == 0) &&
                       (tmp >= 2) && (compressedT[tmp - 1] == -1) &&
                       (compressedT[tmp - 2] == compressedP[P_comp_index])) {
              tmp -= 3;
              P_comp_index--;
              outputFLG = 3;
            } else {
              if (compressedP[P_comp_index] == compressedT[tmp]) {
                tmp -= 1;
                P_comp_index--;
              } else {
                break;
              }
            }
          }
          if (P_comp_index == -1) {
            switch (outputFLG) {
              case 0:
                if (inner == 0) {
                  left_start = total_count[tmp + 1];
                  foundFLG = true;
                } else {
                  right_end = total_count[tmp + 1];
                }
                break;
              case 2:
                if (inner == 0) {
                  left_start = total_count[tmp + 1] + compressedT[tmp + 3] -
                               compressedP[2];
                  foundFLG = true;
                } else {
                  right_end = total_count[tmp + 1] + compressedT[tmp + 3] -
                              compressedP[2];
                }
                break;
              case 3:
                if (compressedP[0] != compressedP[1]) {
                  if (inner == 0) {
                    left_start =
                        total_count[tmp + 1] + compressedT[tmp + 3] - 1;
                    foundFLG = true;
                  } else {
                    right_end = total_count[tmp + 1] + compressedT[tmp + 3] - 1;
                  }
                } else if (compressedP[0] == compressedP[1] &&
                           compressedP[0] != compressedP[2]) {
                  if (inner == 0) {
                    left_start =
                        total_count[tmp + 1] + compressedT[tmp + 3] - 2;
                    foundFLG = true;
                  } else {
                    right_end = total_count[tmp + 1] + compressedT[tmp + 3] - 2;
                  }
                } else {
                  if (inner == 0) {
                    left_start =
                        total_count[tmp + 1] + compressedT[tmp + 3] - 3;
                    foundFLG = true;
                  } else {
                    right_end = total_count[tmp + 1] + compressedT[tmp + 3] - 3;
                  }
                }
                break;
            }
          }
          if (inner == 0 && foundFLG == true) break;
          div_tmp = loc_record.next_loc(most_right);
          if (div_tmp == -1) {
            break;
          } else {
            T_comp_index = div_tmp;
          }
        }
      } else {
        loc_record.init_index();
        int start = loc_record.next_loc(most_right);
        if (start == -1) {
          break;
        }
        if (rightsucceedFLG) {
          for (int i = start; i < comp_T_length;) {
            if (i < comp_T_length - 2 && compressedT[i + 1] == -1 &&
                compressedT[i + 2] >= compressedP[comp_P_length - 1]) {
              int t_s = compressedT[i + 2];
              int p_s = compressedP[comp_P_length - 1];
              if (inner == 0) {
                left_start = total_count[i];
                break;
              } else {
                for (int k = 0; p_s + k <= t_s; k++) {
                  right_end = total_count[i] + k;
                }
              }
            }
            while (true) {
              i = loc_record.next_loc(most_right);
              if (i == -1) {
                zeroFLG = true;
                break;
              } else {
                if (compressedT[i] == most_right && i < comp_T_length - 2 &&
                    compressedT[i + 1] == -1 &&
                    compressedT[i + 2] >= compressedP[comp_P_length - 1]) {
                  break;
                }
              }
            }
            if (zeroFLG) break;
          }
        } else {
          for (int i = start; i < comp_T_length;) {
            if (i < comp_T_length - 2 && compressedT[i + 1] == -1) {
              int t_s = compressedT[i + 2];
              int p_s = comp_P_length;
              if (inner == 0) {
                left_start = total_count[i];
                break;
              } else {
                for (int k = 0; p_s + k <= t_s; k++) {
                  right_end = total_count[i] + k;
                }
              }
            } else {
              if (comp_P_length == 1) {
                if (inner == 0) {
                  left_start = total_count[i];
                  break;
                } else {
                  right_end = total_count[i];
                }
              } else if (comp_P_length == 2 && i < comp_T_length - 1 &&
                         compressedT[i + 1] == most_right) {
                if (inner == 0) {
                  left_start = total_count[i];
                  break;
                } else {
                  right_end = total_count[i];
                }
              } else if (comp_P_length == 3 && i < comp_T_length - 2 &&
                         compressedT[i + 1] == most_right &&
                         compressedT[i + 2] == most_right) {
                if (inner == 0) {
                  left_start = total_count[i];
                  break;
                } else {
                  right_end = total_count[i];
                }
              }
            }
            while (true) {
              i = loc_record.next_loc(most_right);
              if (i == -1) {
                zeroFLG = true;
                break;
              } else {
                break;
              }
            }
            if (zeroFLG) break;
          }
        }
      }
    }
    if (left_start == -1 || right_end == -1) {
      printf("0\n");
    } else if (left_start > right_end) {
      printf("0\n");
    } else if (left_start + left_length - 1 > right_end + right_length - 1) {
      printf("0\n");
    } else {
      printf("%d\n", (right_end + right_length - 1 - left_start + 1));
    }
  }
  return 0;
}
