Đ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 ≤ L ≤ R ≤ 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 ≤ N ≤ 10^5~).
• Dòng thứ hai chứa số nguyên dương ~Q~ (~Q ≤ 10^5~).
• ~Q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~L~, ~R~ (~1 ≤ L ≤ R ≤ 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.

Sample Input 1

abcyzz
3
1 3
2 5
5 6

Sample Output 1

2
4
0

Subtasks