如果我让你查回文你还爱我吗
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

情景对话
牛妹：你爱我吗？
牛牛：爱呀，当然爱呀！
牛妹：那如果我让你查询回文串的话，你还会爱我吗?
牛牛：当然啦，无论发生什么我都会爱你的。
牛妹：给出一个长度为字符串，有个查询，第个查询给出两个整数 ，询问有多少对不同的整数满足，并且构成一个回文串。
牛牛：...（这么难的问题我不会呀┭┮﹏┭┮）。
牛妹：你要是答不出来，就说明你不爱我！！！哼。
牛牛：...（大家快来救救孩子吧┭┮﹏┭┮）。

为了帮助牛牛和牛妹巩固他们坚实的爱情，请你帮助牛牛回答这个问题。
“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。

输入描述:

第一行两个整数。
第二行一个长度为的字符串，中仅包含小写字母。
接下来行每行两个整数表示一个查询。

输出描述:

对于每个查询，输出一行一个整数表示答案。
示例1

输入

复制 
3 3
aba
1 3
1 2
2 2

输出

复制 
4
2
1

说明

{aba}中有{a,b,a,aba}四个回文子串，注意两个{a}出现的位置不同。

备注: