1 //O(n)回文串
2 # include <stdio.h>
3 # include <algorithm>
4 # include <iostream>
5 # include <string>
6 # include <cmath>
7
8 # define For(i,a) for(int (i)=0;i<(a);++(i))
9 using namespace std;
10 const int N=200100;
11
12 int lg[N<<1];
13 char s[N],str[N<<1];
14 int p[N<<1];
15 int rmq[19][N<<1],n,up;
16
17 void pk()
18 {
19 int mx(0),id;
20 rmq[0][0] = p[0] = 0;
21 For(i,up)
22 {
23 if(mx > i)
24 p[i] = min(p[id*2-i], mx-i);
25 else
26 p[i] = 1;
27 while(str[i+p[i]] == str[i-p[i]])
28 p[i]++;
29 if(p[i] + i > mx)
30 {
31 mx = p[i] + i;
32 id = i;
33 }
34 rmq[0][i] = p[i]-1;
35 }
36 }
37 void pre_log()
38 {
39 int i,n;
40 lg[0] = lg[1] = 0;
41 for(i=1; i<N; i++)
42 lg[i*2] = lg[i*2+1] = lg[i]+1;
43 }
44
45 void pre_rmq(int rmq[][N<<1])
46 {
47 int i,k;
48 int rn = (int)floor(log(2*n*2.0)/log(2.0));
49 for(i=1;i<rn;i++)
50 {
51 k = 2*n + 2 - (1<<(i-1));
52 For(j, k)
53 rmq[i][j] = max(rmq[i-1][j], rmq[i-1][j+(1<<(i-1))]);
54 }
55 }
56 int ask_rmq(int rmq[][N<<1],int a,int b) /// [a,b]闭区间
57 {
58 int rq = lg[b-a];
59 return max(rmq[rq][a], rmq[rq][b+1-(1<<rq)]);
60 }
61 void read()
62 {
63 scanf("%s", s);
64 n = strlen(s);
65 str[0] = '$';
66 str[1] = '#';
67 For(i,n)
68 {
69 str[i*2 + 2] = s[i];
70 str[i*2 + 3] = '#';
71 }
72 str[up = n*2 + 2] = 0;
73 pk();
74 pre_rmq(rmq);
75 }
76
77 int doit()
78 {
79 int l,r,ans=0;
80 int high,low=0,mid,gt;
81 scanf("%d %d", &l, &r);
82 high = r-l + 1;
83 while(low <= high)
84 {
85 mid = (low + high) / 2;
86 gt = ask_rmq(rmq, 2*l+mid-1, 2*r-mid+1);
87 if(gt >= mid)
88 {
89 low = mid+1;
90 ans = mid;
91 }
92 else
93 high = mid-1;
94 }
95 return ans;
96 }
97
98 int main()
99 {
100 pre_log();
101 int T,_=0;
102 int q,ans;
103 scanf("%d",&T);
104 while(_++ < T)
105 {
106 read();
107 scanf("%d", &q);
108 while(q--)
109 {
110 ans = doit();
111 printf("%d\n", ans);
112 }
113 }
114 return 0;
115 }