26 chữ cái tiếng Anh in thường được xếp thành một vòng tròn cách đều nhau 1 đơn vị như hình bên. Khoảng cách giữa hai kí tự là số bước đi chuyển ngắn nhất từ kí tự này đến kí tự kia. Ví dụ khoảng cách giữa hai kí tự d và e là 2; khoảng cách giữa a và z là 1.

Khoảng cách của một xâu là khoảng cách lớn nhất giữa hai kí tự bất kì của xâu đó. Ví dụ tính khoảng cách của xâu adc:

• Khoảng cách của a và d là 3.
• Khoảng cách của a và c là 2.
• Khoảng cách của d và c là 1.
  Vậy khoảng cách của xâu adc là \(max(3,2,1) = 3\).

Cho xâu \(S\) gồm \(N\) kí tự được đánh chỉ số từ 1 đến \(N\) và \(Q\) truy vấn, mỗi truy vấn yêu cầu tính khoảng cách của xâu con từ vị trí \(L\) đến vị trí \(R\) trong xâu \(S\) \((1 \leq L \leq R \leq N)\).

Input

• Dòng đầu tiên chứa xâu \(S\) chỉ gồm các kí tự tiếng Anh in thường gồm \(N\) kí tự \((1 \leq N \leq 10^5)\)
• Dòng thứ hai chứa số nguyên dương \(Q\) \((Q \leq 10^5)\)
• \(Q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(L,R\) \((1 \leq L \leq R \leq N)\) mô tả đoạn con của xâu \(S\) cần tính khoảng cách

Output

• Gồm \(Q\) dòng, mỗi dòng gồm một số nguyên là kết quả của truy vấn tương ứng

Example

abcyzz
3
1 3
2 5
5 6

2
4
0

Scoring

• 50% số test ứng với 50% số điểm có \(Q = 1; N \leq 10^3\)
• 20% số test tiếp theo ứng với 20% số điểm có \(Q = 1\)
• 20% số test tiếp theo ứng với 20% số điểm có \(N \leq 10^3\)
• 10% số test còn lại ứng với 10% số điểm không có ràng buộc gì thêm