Một xâu được gọi là xâu đối xứng nếu đọc từ trái sang phải hay đọc từ phải sang trái đều giống nhau.

Cho một xâu S có độ dài N, chỉ gồm các ký tự chữ cái in thường từ a đến z.

Có Q truy vấn, mỗi truy vấn gồm hai số nguyên L và R.

Với mỗi truy vấn, hãy đếm số lượng cặp (X, Y) thỏa mãn:

\(L \le X \le Y \le R.\)
Xâu con từ vị trí X đến vị trí Y của xâu S là một xâu đối xứng.

Nói cách khác, với mỗi đoạn [L, R], hãy đếm số lượng xâu con đối xứng nằm hoàn toàn trong đoạn đó.

Yêu cầu

Với mỗi truy vấn [L, R], hãy in ra số lượng xâu con đối xứng của xâu S nằm trong đoạn từ L đến R.

Input

• Dòng đầu tiên chứa xâu S có độ dài N (\(1 \le N \le 5000\)), chỉ gồm các chữ cái in thường.
• Dòng thứ hai chứa số nguyên Q (\(1 \le Q \le 10^5\)).
• Q dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R (\(1 \le L \le R \le N\)).

Output

• In ra Q dòng.
• Dòng thứ i là số lượng xâu con đối xứng nằm hoàn toàn trong đoạn tương ứng với truy vấn thứ i.

Example

caaaba 
5 
1 1 
1 4
2 3
4 6 
4 5

1 
7
3
4 
2

Scoring

• Subtask 1 (\(20\%\) số điểm): \(N, Q \le 100\).
• Subtask 2 (\(40\%\) số điểm): \(N, Q \le 300\).
• Subtask 3 (\(20\%\) số điểm): \(N, Q \le 2000\).
• Subtask 4 (\(20\%\) số điểm): Không có ràng buộc nào thêm.