Description
PIPI要考考你对回文串的掌握了~
现在有一个长度为n的字符串S，PIPI对此有q个询问，每次询问S中某个连续区间(从1开始)中回文子串的数目。
Input
多组数据。
第一行为两个个整数n,q（1<=n<=1000,1<=q<=100000）
第二行为一个长为n的字符串S。
接下来q行，每行两个整数l,r，表示询问S中区间[l,r]中回文子串的数目。保证l<=r且合法。
Output
对于每个询问输出占一行，输出该区间内回文子串的数目。
HINT
aba中有a,b,c,aba四个回文子串