Điền 26 kí tự Tiếng Anh in thường theo thứ tự từ điển thành một vòng tròn cách đều nhau 1 đơn vị. Khoảng cách giữa hai kí tự là số bước di 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ự '\(a\)' và '\(c\)' 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 \le L \le R \le N\)).

Dữ liệu vào

Dữ liệu vào từ file văn bản KHOANGCACH.INP:

• 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 \le N \le 10^5\)).
• Dòng thứ hai chứa số nguyên dương \(Q\) (\(Q \le 10^5\)).
• \(Q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(L, R\) (\(1 \le L \le R \le N\)) mô tả đoạn con của xâu \(S\) cần tính khoảng cách.

Dữ liệu ra

Kết quả ghi ra file văn bản KHOANGCACH.OUT: 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.

Ví dụ

Ví dụ 1

Đầu vào:

abcyzz
3
1 3
2 5
5 6

Đầu ra:

2
4
0

Giải thích / Giới hạn

Giải thích chi tiết:

• Truy vấn 1 (\(L=1, R=3\)): Xâu con là "abc". Khoảng cách lớn nhất giữa các cặp kí tự trong xâu này là 2 (giữa 'a' và 'c').
• Truy vấn 2 (\(L=2, R=5\)): Xâu con là "bcyz". Khoảng cách lớn nhất là 4 (giữa kí tự 'c' và 'y', đi theo đường c-b-a-z-y là 4 bước).
• Truy vấn 3 (\(L=5, R=6\)): Xâu con là "zz". Hai kí tự giống nhau nên khoảng cách là 0.

Ràng buộc:

• Có 50% số test ứng với 50% số điểm có \(Q = 1; N \le 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 \le 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.