T652666 回文子串的个数

给定一个由小写字母组成的字符串 s，长度为 n（1 ≤ n ≤ 5000）。你需要处理 q 次查询（1 ≤ q ≤ 10^6），每次查询给出两个整数 l 和 r（1 ≤ l ≤ r ≤ n），要求统计字符串 s 的子串 s[l..r] 中包含多少个回文子串。 回文子串定义：如果一个子串正读和反读相同，则称该子串为回文子串。单个字符也被视为回文子串。

第一行包含一个字符串 s（仅由小写字母组成）。 第二行包含一个整数 q，表示查询次数。 接下来 q 行，每行包含两个整数 l 和 r，表示查询的区间。

对于每个查询，输出一个整数，表示子串 s[l..r] 中包含的回文子串数量。

abb中包含4个 a b b bb 这4个