Để đạt mục tiêu giải cao trong kỳ thi Olympic Tin học sinh viên Tina đã học tập và cày code rất chăm chỉ, code 25 tiếng một ngày. Một hôm, sau khi accept được một câu chuỗi rất hay, Tina đã đem câu đó đi đố Luna. Cho một chuỗi gồm các chữ cái viết thường ~s~, hỏi có bao nhiêu xâu con đối xứng trong đoạn ~s[l, r]~. Tuy nhiên Luna đang bận tương tư nên chỉ nhớ tên người nào đó mà không nhớ gì về chuỗi s. Bạn hãy giúp Luna trả lời các câu hỏi này nhé.

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

Input

• Dòng đầu tiên là số lượng ký tự n của xâu ~s~.
• Dòng thứ hai gồm các ký tự chuỗi ký tự viết thường ~s~.
• Dòng thứ ba là số lượng truy vấn q
• Tiếp theo là ~q~ dòng, mỗi dòng gồm 2 số nguyên ~l, r~.

Subtasks

• Subtask 1: ~ 1 \le |s| \le 300, 1 \le q \le 15 ~
• Subtask 2: ~ 1 \le |s| \le 3000, 1 \le q \le 5 ~
• Subtask 3: ~ 1 \le |s| \le 3000, 1 \le q \le 10^6 ~

Output

In ra kết quả gồm ~q~ dòng tương ứng kết quả truy vấn.

Examples

*Input 1 *

7
ababcba 
3
1 3 
2 5
3 7

*Output 1 *

4 
5 
7 

*Input 2 *

10
hikbwhwbki
7
5 7
5 7
4 8
4 9
1 1
5 7
3 9

*Output 2 *

4
4
7
8
1
4
10